http://poj.org/problem?id=1321
题意是给你一个n * n的矩阵，上面有若干块是可以放置棋子的，问你摆放k个棋子的所有可能性。
这里用DFS求解，从第1行到第n行，每行再去试第1列到第n列，尝试是否能放棋子。
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, k, ans, cnt;
char b[10][10];
bool book[10]; // 用来记录每一列是否放置棋子
void DFS(int cur) {
if (cnt == k) {
ans++;
return;
}
if (cur > n)
return;
// 遍历当前行的每一列，尝试放棋子
for (int i = 1; i <= n; ++i) {
if (!book[i] && b[cur][i] == '#') {
book[i] = true;
cnt++;
DFS(cur + 1);
book[i] = false;
cnt--;
}
}
DFS(cur + 1); // 到下一行
}
int main() {
ios::sync_with_stdio(false);
cin.tie(false);
while (cin >> n >> k && n != -1 && k != -1) {
fill(book + 1, book + n + 1, false);
ans = cnt = 0;
for (int i = 1; i <= n; ++i) {
getchar();
for (int j = 1; j <= n; ++j) {
cin >> b[i][j];
}
}
// DFS从第1行 ~ 第n行
DFS(1);
cout << ans << endl;
}
return 0;
}
