网站建设服务58,产品软文范例,网站建设三合一,网站在线seo题目描述 棋盘问题 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 63237 Accepted: 30234Description 在一个给定形状的棋盘#xff08;形状可能是不规则的#xff09;上面摆放棋子#xff0c;棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或… 题目描述 棋盘问题 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 63237 Accepted: 30234Description 在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数n k用一个空格隔开表示了将在一个n*n的矩阵内描述棋盘以及摆放棋子的数目。 n 8 , k n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状每行有n个字符其中 # 表示棋盘区域 . 表示空白区域数据保证不出现多余的空白行或者空白列。 Output 对于每一组数据给出一行输出输出摆放的方案数目C 数据保证C2^31。 Sample Input 2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1Sample Output 2
1Source 解题思路从问题出发可以看出是一个搜索问题棋盘是不规则的而且棋子也不一定是排满的。需要对每一个位置进行可不可以下棋搜索如果可以下要考虑是否安排下棋。考虑到一行或者一列不能下两个棋子对没行进行搜索搜索到可以下的行需要考虑是否将棋子下入改行。最后考虑边界停止搜索的边界有两个一棋盘的边界n、二棋子下完的边界k。 #includeiostream
using namespace std;
int way,result;//way表示已排多少棋子result表示结果
int n,k;
int temp[10];//标记列是否已有棋子
char ch[10][10];
void dps(int l)//深度优先搜索函数
{if(wayk)//棋子排满边界{result;return ;}if(ln)//设置数组边界{return ;}for(int i0;in;i)//考虑第l列的情况{if(ch[l][i]#temp[i]0){temp[i]1;way;dps(l1);//将搜索的节点计算入内的情况temp[i]0;//不将节点计算入内的情况way--;}}dps(l1);//不考虑第l列的情况
}
int main()
{int i,j;while(cinnk(n!-1||k!-1)){//初始化way0;result0;for(i0;in;i)for(j0;jn;j)cinch[i][j];//从第0行开始深度优先搜索dps(0);coutresultendl;}return 0;
}转载于:https://www.cnblogs.com/ke-yi-/p/10175851.html
