dfs 棋盘问题

Description

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

Input

输入含有多组测试数据。

每组数据的第一行是两个正整数，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;
}
           

）