题目
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。
要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 个棋子的所有可行的摆放方案数目 。
输入格式
输入含有多组测试数据。
每组数据的第一行是两个正整数 ，用一个空格隔开，表示了将在一个 的矩阵内描述棋盘，以及摆放棋子的数目。当为-1 -1时表示输入结束。
随后的 行描述了棋盘的形状：每行有 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出格式
对于每一组数据，给出一行输出，输出摆放的方案数目 （数据保证 ）。
数据范围
输入样例：
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
输出样例：
2
1
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <iostream>
#include <cstring>
#include <vector>
#define N 10
using namespace std;
bool row[N], col[N];
int n, m;
int cnt;
void dfs(int u, int s, vector<int> &vec)
{
if (u == m) ++ cnt;
else
{
if (s == vec.size()) return;
int x = vec[s] / n, y = vec[s] % n;
if (!row[x] && !col[y])
{
row[x] = col[y] = true;
dfs(u + 1, s + 1, vec);
row[x] = col[y] = false;
}
dfs(u, s + 1, vec);
}
}
int main()
{
while (cin >> n >> m, ~n)
{
memset(row, false, sizeof row);
memset(col, false, sizeof col);
vector<int> vec;
cnt = 0;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
{
char c; cin >> c;
if (c == '#') vec.push_back(i * n + j);
}
dfs(0, 0, vec);
cout << cnt << endl;
}
}
|
