poj 1321棋盘问题

题目链接：http://poj.org/problem?id=1321

dfs经典模板：

 1 dfs()
 2 {
 3     if条件判断——（到终点）
 4     {
 5         操作……
 6         return;
 7     }
 8     if……省略一些条件判断（剪枝优化，比如一些没必要的continue或者计算过的子问题的标记备忘录直接存取）
 9     for()
10         if……满足条件的筛选
11         修改标记；
12         dfs();
13         改回标记；
14 }

分析：

接下来是dfs递归的核心部分：
不妨从第0行开始，这时候需要处理的是k个棋子，对第0行遍历，找到一个满足题意的‘#’区域后，为了避免列重复，以后这一列都不能用了，建立一个一维数组vis数组标记当前列，然后深层搜索，这时候，就要从第1行开始搜索了（正因为这样，vis才不用存储行是否用过的冲突问题），此时需要处理的是k-1个棋子，第1行所有元素都遍历，找‘#’，只不过对于之前vis标记过得那一列，我们也不选用，找到后，再次标记，然后dfs……………………dfs进入第i行，对第i行遍历，当前需要处理的是k-i个棋子的问题，筛掉非棋盘区域和之前标记过得列，找到’#’，标记，然后dfs()………………知道某一次dfs进入后，发现当前处理棋子数量为0，说明到头了，这是找到了一种方法，count++，return，假设这是第一次return，那么将返回到第k-1行，继续寻找满足的‘#’，重复…………知道某一次return会到第count == k行了，那么，将从第1行继续作为dfs的第一次起始，这就相当于改变控制了dfs起始的位置。

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 int n,k;
 7 int mp[10][10];
 8 int vis[10];
 9 
10 int ans = 0;
11 
12 void dfs(int row,int cnt)
13 {
14     if(cnt == k)
15     {
16         ans++;
17         return ;
18     }
19     for(int i = row; i < n; i++)
20     {
21         for(int j = 0; j < n; j++)
22         {
23             if(mp[i][j]=='#' && !vis[j])
24             {
25                 vis[j] = 1;
26                 dfs(i+1,cnt+1);
27                 vis[j] = 0;
28             }
29         }
30     }
31 }
32 
33 int main()
34 {
35     while(scanf("%d%d",&n,&k) && (n!=-1 && k!=-1))
36     {
37         getchar();
38         for(int i = 0; i < n; i++)
39         {
40             for(int j = 0; j < n; j++)
41             {
42                 scanf("%c",&mp[i][j]);
43             }
44             getchar();
45         }
46         memset(vis,0,sizeof(vis));
47         ans = 0;
48         dfs(0,0);
49         printf("%d
",ans);
50     }
51     return 0;
52 }