题意:给出棋盘分布情况和棋子数,要求任意两个棋子不能在同一行或者同一列。
思路:逐行搜索按列标记,就能保证棋子摆放的位置正确。
这道题开始用方向数组的方法做,结果不对,后来上网看下别人代码,参考了这种方法,但是如果找到了一种情况,此时该行所对应的所有列都已经没有符合的位置了,也搜不下去了。。又卡在这里了。最后看了下,又加了一条语句 dfs(i+1,num); 移动到下一行,果断过了。
#include<iostream> using namespace std; char map[10][10]; bool vis[10];//按列标记用的数组 int n,k; int ans; void dfs(int i,int num) { if(num==k) {ans++;return;} if(i==n) return;//搜到最后,跳出。 for(int g=0;g<n;g++) { if(!vis[g]&&map[i][g]=='#') { vis[g]=1; dfs(i+1,num+1); vis[g]=0; //printf("回溯\n"); } } dfs(i+1,num);//到下一行继续搜索。 } int main() { while(scanf("%d%d",&n,&k)!=EOF) { if(n==-1&&k==-1) break; for(int i=0;i<n;i++) cin>>map[i]; memset(vis,0,sizeof(vis)); ans=0; dfs(0,0); printf("%d\n",ans); } }