python/C++专题课程/深度优先搜索/POJ_1321.cpp

#include <bits/stdc++.h>

using namespace std;

int n, k, vis[15], ans;
char mat[15][15];

//cur : 当前检测行
//num : 已经摆放的棋子数
void dfs(int cur, int num) {
    if (num == k) {
        ans++;
        return;
    }

    for (int i = cur; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == '#' && !vis[j]) {
                vis[j] = 1;
                dfs(i + 1, num + 1);
                vis[j] = 0;
            }
        }
    }
}

int main() {
    while (~scanf("%d %d%*c", &n, &k) && n != -1 && k != -1) {
        memset(vis, 0, sizeof(vis));
        int i;
        for (i = 0; i < n; i++)
            gets(mat[i]);

        ans = 0;
        dfs(0, 0);
        printf("%d\n", ans);
    }
    return 0;
}