信息可视化网站,专业网站运营,南通网站建设心得,网站建设 上海网Problem Descrption
在一个给定形状的棋盘#xff08;形状可能是不规则的#xff09;上面摆放棋子#xff0c;棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列#xff0c;请编程求解对于给定形状和大小的棋盘#xff0c;摆放k个棋子的所有可行的…Problem Descrption
在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放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 -1
Sample Output
2
1
问题链接http://poj.org/problem?id1321
在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放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 -1
Sample Output
2
1
问题链接http://poj.org/problem?id1321
问题分析DFS思想
AC代码
#includeiostream
using namespace std;
int n, k, ans;
char str[10][10];
int vis[100];void dfs(int r, int k)
{if(k0)//判断边界此时棋子已经放完{ans;return;}for(int ir; in; i)//每次都从放过棋子下一行开始搜索保证不重复{for(int j0; jn; j){//循环保证行不重复check保证列不重复if(str[i][j]. || vis[j]1)continue;//不满足条件直接跳过vis[j] 1;//标记dfs(i1, k-1);//继续下一次标记vis[j] 0;//恢复初始状态}}
}int main(void)
{while(1){scanf(%d %d, n, k);getchar();if(n-1 k-1) break;memset(str, \0, sizeof(str));memset(vis, 0, sizeof(vis));ans 0;for(int i0; in; i){for(int j0; jn; j)str[i][j] getchar();getchar();}dfs(0, k);//从第0行开始放此时手中还剩k个棋子printf(%d\n, ans);}return 0;
}
