【题目描述】

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

【输入】

输入含有多组测试数据。

每组数据的第一行是两个正整数 $n,k$ ，用一个空格隔开，表示了将在一个 $n×n$ 的矩阵内描述棋盘，以及摆放棋子的数目。 ( $n≤8,k≤n$ ) 当为 $−1$ 时表示输入结束。

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

【输出】

对于每一组数据，给出一行输出，输出摆放的方案数目 $C$ （数据保证 $C<231$ ）。

【输入样例】

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

【输出样例】

2 1

代码

#include <stdio.h>
int m[8][9];
//m表示输入的棋盘
int a[8] = {-1, -1, -1, -1, -1, -1, -1, -1}, b[8], c[16], d[16], s;
//a[i]表示第i个棋子放的位置
//b[i]==1表示行上有棋子，0没有
//c[i]西北-东南走向对角线，具体值见b[i]...
//d[i]东北-西南走向对角线，具体值见b[i]...
int n, k;//见题目
int t(int n, int x){
	//棋子位于n行x列
	if (m[n][x] == '.'){//空白区域
		return 0;
	}
	if (b[n]){//在第n行上有棋子
		return 0;
	}
	if (c[x + 7 - n]){//在西北-东南走向对角线上有棋子
		return 0;
	}
	if (d[x + n]){//在东北-西南走向对角线上有棋子
		return 0;
	}
	return 1;
}
int g(int x, int l){
	//第x个棋子，x定义域[0, k)
	//l是从第l行开始放
	if (x == k){//结束
		return 1;//方案数 + 1，结束递归
	}
	int s = 0, o = n - k + x + 1;
	//s方案数，o放到第n - k + x行结束
	for (int j = l; j < o; j++){//第x个棋子放在第j行
		if (!a[j]){//第j行没棋子
			for (int i = 0; i < 8; i++){
				if (t(i, x)){//符合题目条件
					a[j] = i;//放棋子
					b[i] = 1;//放标记 行
					c[j + 7 - i] = 1;//放标记 西北-东南走向对角线
					d[j + i] = 1;//放标记 东北-西南走向对角线
					s += g(x + 1, j + 1);
					//消除标记并回溯
					a[j] = -1;
					b[i] = 0;
					c[j + 7 - i] = 0;
					d[j + i] = 0;
				}
			}
		}
	}
	return s;
}
int main(){
	//按照题目给的输入
	scanf("%d%d", &n, &k);
	while (n != -1 || k != -1){
		for (int i = 0; i < n; i++){
			scanf("%s", m[i]);
		}
		printf("%d\n", g(k, 0));
		scanf("%d%d", &n, &k);
	}
	return 0;
}

有问题吗？