题意:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
Output
对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
思路:这题只需要深搜,每次从上一个放棋子地方的下一行开始寻找可以放棋子的地方,当发现该点时,记录行数,并更新棋盘,将于此点同行同列的都更新为'.',如果找不到,则返回,当把所有棋子都放上去的时候,则找到一个接,计数+1,就这样进行搜索,可以保证AC。由于题意中明确的提出C<2^31,这样int类型就能满足,设计时就不用考虑这个数据类型了!
代码如下:
#include<iostream>
using namespace std;
const int Max = 10;
bool board[Max][Max], row[Max], col[Max]; // row[i],col[j]分别记录第i行,第j列被访问了没有。
int len, num, ans;
void dfs(int depth, int start_line)
{
if(depth == num)
{
ans ++;
return;
}
for(int i = start_line + 1; i <= len; i ++)
for(int j = 1; j <= len; j ++)
if(board[i][j] == true && row[i] == false && col[j] == false)
{
row[i] = true;
col[j] = true;
dfs(depth + 1, i);
row[i] = false;
col[j] = false;
}
}
int main()
{
int i, j;
char c;
while(1)
{
cin >> len >> num;
if(len == -1 && num == -1)
break;
memset(board, false, sizeof(board));
for(i = 1; i <= len; i ++)
for(j = 1; j <= len; j ++)
{
cin >> c;
if(c == '#')
board[i][j] = true;
}
ans = 0;
memset(row, false, sizeof(row));
memset(col, false, sizeof(col));
int start_line = len - num + 1; // 第一颗棋子的位置可能在 1 ~ start_line 行之间。
for(i = 1; i <= start_line; i ++)
for(j = 1; j <= len; j ++)
if(board[i][j] == true)
{
row[i] = true;
col[j] = true;
dfs(1, i);
row[i] = false;
col[j] = false;
}
cout << ans << endl;
}
return 0;
}
关于代码中的回溯问题,现在说实在的不能理解啊~!真的想了好久,还是不懂!要向别人去请教一下才能懂!!
分享到:
相关推荐
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
dfs中的回溯法,poj2488骑士游历,主要是回溯要将所有的点都遍历到。
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
放炮问题,北大网站 POJ 1185 算法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
北大POJ初级-简单搜索 解题报告+AC代码
poj2599,简单dfs可以过此题,按顺序搜到任意可行解即可。
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ1048,加强版的约瑟夫问题 难度中等
是算法设计与分析课程的 回溯算法 POJ2000金币问题的解决方案 有两种解法在里面 值得大家关注一下 可以拿去参考参考 有什么错误还忘大家指出 谢谢