简单搜索之棋盘问题

题意：

在一个棋盘内放k个棋子，每一行每一列都最多只能有一个棋子，求方法数，‘#’为可放的地方。

思路：

直接暴力深搜枚举所有情况即可，每一行选择一个点向下继续深搜，同时a[]储存该列是否已有棋子。

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k,summ; int a[10][10],b[10]; void dfs(int now,int step) { if(step==k) { summ++; return; } if(now==n) { return; } for(int i=0;i<n;i++) if(a[now][i]==1&&!b[i]) { b[i]=1; dfs(now+1,step+1); b[i]=0; } dfs(now+1,step); } int main() { char s[10]; while(scanf("%d%d",&n,&k)!=EOF) { if(n==-1&&k==-1) break; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); summ=0; for(int i=0;i<n;i++) { scanf("%s",s); for(int j=0;j<n;j++) if(s[j]=='#') a[i][j]=1; } dfs(0,0); printf("%d\n",summ); } return 0; } 注意:没有办法通过for循环进行搜索，必须通过bfs函数搜索。