棋盘问题 (POJ - 1321)

题面

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

输入

输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出

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

样例输入

12 1
2#.
3.#
44 4
5...#
6..#.
7.#..
8#...
9-1 -1

样例输出

12
21

提示

无

思路

按行讨论，保存列的访问状态

代码

 1using namespace std;
 2typedef long long ll;
 3const int inf = 0x3f3f3f3f;
 4const int N = 8;
 5
 6char b[N][N] = {0};
 7bool vis[N] = {0};
 8int n, k, ans = 0;
 9
10void dfs(int x, int cnt) {
11    if(cnt>=k) {
12        ans++;
13        return ;
14    }
15    for(int i=x; i<n; i++) {
16        for(int j=0; j<n; j++) {
17            if(b[i][j]=='#' && !vis[j]) {
18                vis[j] = true;
19                dfs(i+1, cnt+1);
20                vis[j] = false;
21            }
22        }
23    }
24}
25
26int main(void) {
27    while(scanf("%d%d", &n, &k)==2 && n!=-1 && k!=-1) {
28        ans = 0;
29        memset(vis, 0, sizeof(vis));
30
31        for(int i=0; i<n; i++)
32            for(int j=0; j<n; j++)
33                scanf(" %c", &b[i][j]);
34
35        dfs(0, 0);
36        printf("%d\n", ans);
37    }
38    return 0;
39}