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;
}