[POJ 1321] 棋盘问题

题目链接：http://poj.org/problem?id=1321
注意代码中的注释。
 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 int n,k,total,ans;
 6 bool vis[10];
 7 char maze[10][10];
 8 
 9 void DFS(int cur)
10 {
11     /*
12      * 先判断是不是达到了总数，在判断是不是越界
13      * 因为是不是达到总数是上一个状态的情况，是否越界试下一个状态的情况
14      */
15     if(total == k)
16     {
17         ans++;
18         return ;
19     }
20     if(cur>=n)
21         return ;
22     for(int j=0;j<n;j++)
23     {
24         if(maze[cur][j] == '#' && !vis[j])
25         {
26             vis[j] = 1;
27             total++;
28             DFS(cur+1);  //勿写成DFS(++cur): 如果下一行不行，那么你现在的状态仍然是下一行的状态，而不是刚才的状态。
29             vis[j] = 0;
30             total--;
31         }
32     }
33     DFS(cur+1); //就算上面的所有列都不合适，你也得跳到下一行去。
34 }
35 int main()
36 {
37     while(~scanf("%d%d",&n,&k)&&(n!=-1&&k!=-1))
38     {
39         for(int i=0;i<n;i++)
40             scanf("%s",maze[i]);
41         memset(vis,0,sizeof(vis));
42         total = ans = 0;
43         DFS(0);
44         printf("%d
",ans);
45     }
46     return 0;
47 }