poj-1321 棋盘问题（dfs）
Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 63659 Accepted: 30423
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
蔡错@pku
思路
- 下子方案数就相当于遍历图的不同遍历数，用 dfs 变形。
- 理解以下数据还有样例应该差不多了
3 2 #.. .#. ..# 3
3 2 #.. .## ..# 4
AC 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char mp[8][8]; int v[8]; int n,k,w,r;//状态计数器 r void dfs(int x)//逐行深搜，x 为当前搜索行 { if(w==k)//下子数 w { r++;return; } if(x==n)return; for(int i=0;i<n;i++) { if(v[i]!=1&&mp[x][i]=='#') { v[i]=1; w++; dfs(x+1); w--; v[i]=0; } } dfs(x+1);//搜索下一行 } int main() { while(cin>>n>>k) { if(n==-1&&k==-1) return 0; memset(mp,0,sizeof(mp)); memset(v,0,sizeof(v)); for(int i=0;i<n;i++) cin>>mp[i]; w=0;r=0; dfs(0); cout<<r<<endl; } } |
|---|
腾讯云开发者
