棋盘问题 poj1321
题目大意：给你一个n*n的棋盘，上面有一些格子可以下棋。求在这个棋盘上放置满足条件者的方案数。放在上面的k个棋子，满足任意两个棋子，既不同行，也不同列。
注释：1<=k<=n<=8.
想法：啊哈哈！！poj上的中文题，怎么能不A掉呢？但是我开始的想法比较的偏见，在这里说一下，已做纪念。我开始想的是，当每一行都有空格的时候，我期望求出填入n个棋子的方案数，然后乘上组合数$C_{n}^{k}$。然后，必然是wa的。因为有这样一组反例.
2 1
#.
#.
如果按照我的方法这种情况的方案数就是0,但是我们显然可以找到两种。就是说不能对于任意一种情况都可以完整地填入n个棋子，这组反例是看了Discuss然后发现的。所以，发现了这组反例之后，我决定... ...不再任何剪枝，直接爆搜！其实我们可以发现这题和n皇后差不多，建议A掉了n皇后再做这道题。注意这道题没有限制斜边的情况，所以不用像n皇后一样弄3个bool数组来判定情况。
最后，附上丑陋的代码... ...
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int ans; 6 bool v[10]; 7 char s[10][10]; 8 int before[10]; 9 int n,k,all; 10 void dfs(int x) 11 { 12 if(all==k) 13 { 14 ans++; 15 return; 16 } 17 if(x==n+1) 18 { 19 return; 20 } 21 for(int i=1;i<=n;i++) 22 { 23 if(s[x][i]==‘#‘&&!v[i]) 24 { 25 v[i]=1; 26 all++; 27 dfs(x+1); 28 v[i]=0; 29 all--; 30 } 31 } 32 dfs(x+1); 33 } 34 int main() 35 { 36 while(~scanf("%d%d",&n,&k)) 37 { 38 all=0; 39 ans=0; 40 if(n==-1&&k==-1) return 0; 41 memset(v,false,sizeof(v)); 42 memset(s,0,sizeof(s)); 43 for(int i=1;i<=n;i++) 44 { 45 scanf("%s",s[i]+1); 46 } 47 dfs(1); 48 printf("%d\n",ans); 49 } 50 }
小结：当你想到了一个比较强的结论的时候，记得不要直接码，先看一看可不可以直接用一组比较简单的情况卡掉。一般情况下，一些比较优秀的算法在小数据是不怎么太实用的。如果一个c++算法在小数据是错误的，这个算法就可以通过等量的放大，就可以将这个算法D掉。