1.6.3 棋盘问题1

Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。

每组数据的第一行是两个正整数，n,k用一个空格隔开，表示了将在一个n∗n的矩阵内描述棋盘，以及摆放棋子的数目。

当为−1−1时表示输入结束。

随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目CCC。

Sample Input 1

2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1

Sample Output 1

2 1

//DFS

//类似于八皇后的一道多了一些限制的题

#include

#include

#include

using namespace std;

const int N = 20;

char g[N][N]; //存储输入棋盘

int ans; //存储答案

int n, k;

int m; //存储已近放入棋盘的棋子数

bool line[N]; //存储当前列上有没有其他棋子

void dfs(int x)

{

if(m == k) //当棋子放光的时候

{

ans++;

return;

}

if(x == n) //防止越界

return;

for(int i = 0; i < n; i++) //直接dfs简单完事 按着列的顺序依次向下

if(!line[i] && g[x][i] == '#')

{

line[i] = true;

m++; //记录放入的棋子数

dfs(x + 1);

line[i] = false; //还原初始状态

m--;

}

dfs(x + 1);

//这个是关键，因为 k <= m，因此可能有的行不能放棋子，所以我们要手动舍弃行，直接进入下一行，以免有的情况被遗漏

}

int main()

{

while(scanf("%d%d", &n, &k) && n != -1 && k != -1)

{

ans = m = 0;

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

cin >> g[i][j];

dfs(0);

cout << ans << endl;

}

return 0;

}

大家可以比划着自己手动模拟一下。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。