POJ 1321 棋盤問題：DFS 另一種實現細節

題目同 3343，此處提供另一種 DFS 寫法與細節註釋

關鍵在於「行變換」而非方向陣列。對每一行，嘗試放置或不放置；列用 vis[] 記錄。注意遞歸順序與剪枝。

代碼 (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 10;
char maps[maxn][maxn];
int vis[maxn], n, k, ans;

void dfs(int x, int cnt) {
    if (cnt == k) { ans++; return; }
    if (x > n) return;
    for (int i = 1; i <= n; i++) {
        if (maps[x][i] == '#' && !vis[i]) {
            vis[i] = 1;
            dfs(x + 1, cnt + 1);
            vis[i] = 0;
        }
    }
    dfs(x + 1, cnt); // 當前行不放棋子
}

int main() {
    while (scanf("%d%d", &n, &k) != EOF) {
        if (n == -1 && k == -1) break;
        ans = 0;
        for (int i = 1; i <= n; i++) scanf("%s", maps[i] + 1);
        memset(vis, 0, sizeof(vis));
        dfs(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}