http://poj.org/problem?id=1321
題意是給你一個(gè)n * n的矩陣，上面有若干塊是可以放置棋子的疤孕，問(wèn)你擺放k個(gè)棋子的所有可能性商乎。
這里用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]; // 用來(lái)記錄每一列是否放置棋子
void DFS(int cur) {
if (cnt == k) {
ans++;
return;
}
if (cur > n)
return;
// 遍歷當(dāng)前行的每一列专控，嘗試放棋子
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;
}
