poj1321棋盘问题

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 int n,k,count;
 6 char map[20][20];
 7 int vis[20];//标记某列是否被访问
 8 void dfs(int r,int c)
 9 {
10     if(c==0)//递归边界，当所有棋子都放的合法，计数加一
11     {
12         count++;
13         return;
14     }
15     if(n-r+1<c) return;//当剩余行小于剩余棋子数，退出
16     else dfs(r+1,c);//else 继续
17     if(c>0)
18     {
19         for(int i=1;i<=n;i++)
20         {
21             if(map[r][i]=='#'&&!vis[i])//找到合法的列
22             {
23                 vis[i]=1;//标记已访问
24                 dfs(r+1,--c);//递归
25                 vis[i]=0;
26                 ++c;
27             }
28         }
29     }
30 }
31 int main()
32 {
33     while(cin>>n>>k)
34     {
35         int i,j;
36         if(n==-1&&k==-1)
37             break;
38         for(i=1;i<=n;i++)
39         {
40             for(j=1;j<=n;j++)
41                cin>>map[i][j];
42         }
43         memset(vis,0,sizeof(vis));
44         count=0;
45         dfs(1,k);//从第一行开始递归，让第一行放第K个棋子
46         cout<<count<<endl;
47 
48     }
49     return 0;
50 }
View Code