POJ 1321 棋盘问题(DFS板子题，简单搜索练习)
POJ 1321 棋盘问题(DFS板子题，简单搜索练习)
棋盘问题
Time Limit: 1000MS | Memory Limit: 10000K | |
|---|---|---|
Total Submissions: 44012 | Accepted: 21375 |
Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1Sample Output
2
1Source
题目链接：http://poj.org/problem?id=1321
分析：
这个题目的大意是给定一个棋盘和给定我们需要摆放的棋子的数目，然后问我们有几种摆放方式。首先我们可以明确这是一个深度搜索的题目，与八皇后问题相似。我们建立一个函数DFS用来累计可行的方案数，我们走过一列我们就把它标记下来下次的时候就不可以再摆放在这一列（因为题目要求不可以将棋子摆放在同一行和同一列）
然后就从下一行开始寻找可行的地方，直到我们摆放的棋子数与我们被要求摆放的棋子数相同时，我们就将方案数进行一次++，然后在进行递归下去。
DFS板子题，还在熟练中，争取达到闭着眼睛三分钟敲出板子！
此题我每一步给出详细解释，新手学习，大神见谅！
下面给出详解代码：
1 #include<iostream>
2 #include <algorithm>
3 #include <stdio.h>
4 #include <string.h>
5 using namespace std;
6 int visit[20];
7 char mp[20][20];
8 int ans;//ans表示方案数
9 int k;//k表示棋子数目
10 int n;//n表示棋盘的大小
11 int DFS(int x,int y)
12 {
13 if(y>=k)//判断是否棋子已经用完，如果用完，记录方案数加1,然后直接返回0
14 {
15 ans++;
16 return 0;
17 }
18 for(int i=x;i<n;i++)
19 {
20 for(int j=0;j<n;j++)
21 {
22 if(!visit[j]&&mp[i][j]=='#')//标记数组仅仅标记某一列上是否有棋子，因为每次递归下一列，所以每一列不会有冲突，只需判断这一列上是否有其他棋子
23 {
24 visit[j]=true;//如果该位置该列没被标记且为棋盘，那么在这里放上棋子，并标记，
25 DFS(i+1,y+1);//搜索下一列
26 visit[j]=false;//还要注意修改标记后递归回来要及时复原
27 }
28 }
29 }
30 return 0;
31 }
32 int main()
33 {
34 while(cin>>n>>k)
35 {
36 if(n==-1&&k==-1)
37 break;
38 memset(visit,false,sizeof(visit));
39 memset(mp,false,sizeof(mp));
40 for(int i=0;i<n;i++)
41 cin>>mp[i];
42 ans=0;
43 DFS(0,0);
44 cout<<ans<<endl;
45 }
46 return 0;
47 }多年以后重写此题，想出了另外一种解决办法！
题目意思很明了，其中'#'可以放棋子，'.'不能，并且同一行或同一列不能放两个棋子，对于数据一游两种放法（'*'代表放的棋子）
*.
#.
或
#.
.*
对于数据二只有一种情况
...*
..*.
.*..
*...这题只需要深搜，每次从上一个放棋子地方的下一行开始寻找可以放棋子的地方，
当发现该点时，记录行数，并更新棋盘，将于此点同行同列的都更新为'.'，
如果找不到，则返回，当把所有棋子都放上去的时候，则找到一个接，计数+1，就这样进行搜索，可以保证AC
1 #include <iostream>
2 using namespace std;
3 struct p{
4 char s[10][10];//棋盘
5 int beforerow;//上一个棋子的行数
6 };
7 //st表示开始搜索的棋子所在的那一行,resnum表示剩余可放的棋子数
8 int n,resnum;//n表示当前的棋盘大小为n*n,k表示可放的总棋子数
9 int ans;//摆放的所有可能数
10 void DFS(p temp,int resnum)
11 {
12 if(resnum==0)//如果剩余棋子数量等于0,说明所有棋子都已经放好了,答案数+1返回
13 {
14 ans++;
15 return;
16 }
17 //否则就得从当前棋子的下一行开始搜索
18 //并且我们知道棋子数k大于行数n的情况显然是不存在的,有了肯定是无解情况,这里就不需要讨论这个问题
19 int i,j;
20 for(i=temp.beforerow+1;i<=n-resnum;i++)
21 {
22 for(j=0;j<n;j++)
23 {
24 if(temp.s[i][j]=='#')
25 {
26 p temp1;
27 temp1=temp;
28 temp1.beforerow=i;//记下改点的行数
29 int k;
30 for(k=i+1;k<n;k++)//更新棋盘
31 {
32 temp1.s[k][j]='.';
33 }
34 DFS(temp1,resnum-1);//放好一个棋子继续搜
35 }
36 }
37 }
38 }
39 int main()
40 {
41 while(cin>>n>>resnum)
42 {
43
44 if(n==-1&&resnum==-1)
45 break;
46 ans=0;
47 p temp;
48 temp.beforerow=-1;//此时还未放棋子,初始化为-1
49 for(int i=0;i<n;i++)
50 {
51 cin>>temp.s[i];
52 }
53 DFS(temp,resnum);
54 cout<<ans<<endl;
55 }
56 return 0;
57 }腾讯云开发者
