棋盘问题

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
2

1

code

#include "stdio.h"
#include "string.h"
#define MAXN 10
char matrix[MAXN][MAXN];

int visited[MAXN];

int count = 0;

void DFS (int cur,int k,int n,int m) {//深度优先遍历
	int i;
	if (k == m) {
		count++;
		return;
	}
	if (cur >= n) {//在棋盘的范围里面找不到解。
		return;
	}
	for (i = 0;i < n;i++) {
		if (!visited[i] && '#' == matrix[cur][i]) {//找到一个位置
			 visited[i] = 1;//标记第i列有棋子。
			 DFS (cur+1,k,n,m+1);
			 visited[i] = 0;//恢复到初始状态。
		}	
	}
	DFS(cur+1,k,n,m);//这一行的作用有两个:1:,该行有.和#的情况,用来排除这一行(这一行可以放棋子,但是不一定放),2:当所有的区域都是.的情形(如果没有这一行,深度优先就无法向下进行)。
}
int main () {
	int n,k;
	while (scanf ("%d%d",&n,&k),n != -1 && k != -1) {
		int i,j;
		for (i = 0;i < n;i++) {
			getchar();
			for (j = 0;j < n;j++) {
				scanf ("%c",&matrix[i][j]);
			}
		}
		count = 0;
		memset(visited,0,sizeof(visited));
		DFS (0,k,n,0);
		printf ("%d\n",count);
	}
	return 0;
}
相关文章
相关标签/搜索