第一题：棋盘问题（和八皇后差不多）

题目描述:

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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

2
1

Solving Code:

#include <cstdio>
#include <cstring>

const int maxn = 10;
int n, k, ans, col[maxn];
char mp[maxn][maxn];
void dfs(int row, int cnt){
	if(k == cnt){
		ans++;
		return ;
	}
	if(row >= n)
		return ;
	for(int i = 0;i < n;i++){
		if('#' == mp[row][i] && !col[i]){
			col[i] = 1;
			cnt++;
			dfs(row + 1, cnt);
			cnt--;
			col[i] = 0;
		}
	}
	dfs(row + 1, cnt);
}

int main(){
	while(~scanf("%d %d",&n,&k) && -1 != n && -1 != k){
		char c = getchar();
		for(int i = 0;i < n;i++){
			scanf("%s",mp[i]);
			char ch = getchar();
		}
		dfs(0, 0);
		printf("%d\n",ans);
		ans = 0;
		memset(col, 0, sizeof(col));
	}
	return 0;
}

算法分析：

首先我们回顾一下n皇后问题：在n * n的棋盘上拜访n个皇后，要求n个皇后两两不同行也不同列也不同对角线，问有多少摆放方案？

我们当时的解法是：
首先要有一个check()函数用来判断当前行的下棋方案是否合法，这里有O(n)的算法也有O(1)的算法，O(1)的就是去考察对角线的规律，如下图：

同样的对于另一条对角线：

所以可以轻松得到O(1)的check()函数：

int row[maxn] = col[maxn] = {0};
int diag1[2 * maxn] = diag2[maxn] = {0};
if(!row[dx] && !col[dy] && !diag1[dx + dy - 1] && !diag2[dy - dx + n]){
	row[dx] = col[dy] = diag1[dx + dy - 1] = diag2[dy - dx + n] = 1;
	dfs(dx, dy);
	row[dx] = col[dy] = diag1[dx + dy - 1] = diag2[dy - dx + n] = 0;
}// 一个if就搞定了，在O(1)下完成check！

上面的代码只是一个示范，我们来写一下n皇后代码：

#include <cstdio>

int n, ans, col[10], diag1[20], diag2[20];
void dfs(int row){
	if(row == n + 1){
		ans++;
		return ;
	}
	for(int i = 1;i <= n;i++){
		if(!col[i] && !diag1[row + i - 1] && !diag2[row - i + n]){
			col[i] = diag1[row + i - 1] = diag2[row - i + n] = 1;
			dfs(row + 1);
			col[i] = diag1[row + i - 1] = diag2[row - i + n] = 0;
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(1);
	printf("%d",ans);
	return 0;
}

复习完毕，我们来分析算法：

我们n皇后里要求拜访n个皇后到棋盘上去，这就说明每一列每一行都是有一个棋子的，所以我们只需要按行去做dfs，然后一行行的去搞，如果这行能够解决，就立马摆放上去，然后递归去做下一行，然后用标记数组去标记！

但是这个题呢？我们有n * n的棋盘但是只有k个棋子，也就是说明我们不需要把棋盘全部放满！那么我们的递归出口就有：

if(k == cnt){
	ans++;
	return ;
}

但是如果我们按照行去做dfs，那么就有棋盘边界：

if(row >= n)
	return ;

既然是皇后问题，那么就有回溯，因为如果我们k个棋子都摆放完毕了，或者说是下一步没办法继续摆放了，我们就需要去回过头去调整之前的策略，因为只有把之前的调整了，下一步才能正确的摆放好，所以必须回溯到下一步能到新地方为止。

递归回溯：

for(int i = 0;i < n;i++){
	if(!col[i] && '#' == mp[row][i]){
		col[i] = 1;
		cnt++;
		dfs(row + 1, cnt);
		cnt--;//回溯
		col[i] = 0;//回溯
	}
// 在第i列发现可以下的位置，就下下去，然后递归，如果发现后续失败
// return ；就会让程序到递归函数的下一步，所以我们在递归后回溯
// 如果递归成功，则不会回溯
}// 试探0 - n 列

//如果这n列都不ok呢？因为我们是n * n的棋盘放k个棋子，所以可能出现这种情况
// 那么直接下一行递归开始即可
dfs(row + 1, cnt);