dfs 棋盘问题
Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
Sample Output
21
这个问题实际上是一个假双dfs（即首先对每一行dfs，在对整体dfs
）
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int n, k;
char maps[10][10];
int x[8];
int putn;
int countn;
bool cherk(int i, int j)
{
for (int k = 0; k < i; k++)//检查第i行之前的行数有没有被标记过的并且和该点是一列的点
{
if (x[k] == x[i])return false;
}
if (maps[i][j] == '.')return false;//检查这一点是否是可以放置棋子的点
return true;
}
void dfs(int i)
{
if (putn >= k)
{
countn++;
return;
}
if (i > n-1)
{
return;
}
for (int j = 0; j < n; j++)//在在该行放置棋子的情况下，寻找该行里面能够放置棋子的地方
{
x[i] = j;//标记i行 j列
if (cherk(i, j))
{
++putn;//在当前的落点放置棋子的情况
dfs(i + 1);//在放置在该位置的前提下dfs下一行可能的落点；
x[i] = -1;//取消标记继续搜索该行其他可能的落点
--putn;//不在该处放置棋子的 在该行该落点之后的落点放置棋子的情况
}
else { x[i] = -1; continue; }
}
dfs(i + 1);//该行不落棋子的情况下 ，继续dfs下一行
}
int main()
{
while (~scanf("%d %d", &n, &k))
{
if (n == -1 && k == -1) { break; }
countn = 0;
putn = 0;
memset(x, -1, sizeof(x));
memset(maps, 0, sizeof(maps));
for (int i = 0; i < n; i++)
{
scanf("%s", maps[i]);
}
dfs(0);
printf("%d\n", countn);
}
return 0;
}）
