POJ 1321 棋盤問題：DFS 放置不相互攻擊棋子

問題描述

n×n 棋盤 (n≤8)，'#' 為可放區域，'.' 為禁區。放 k 個棋子 (k≤n)，任意兩子不同行不同列。求方案數。

DFS 回溯

按行遞歸，每行選擇：不放、或在某列放（該列未被佔用且為 '#'）。狀態：row 當前行，cnt 已放數，col_used[8] 列佔用標記。

代碼實現

#include 
using namespace std;
int n, k, ans, col[8];
char g[8][9];

void dfs(int r, int cnt) {
    if (cnt >= k) { ++ans; return; }
    if (r >= n) return;
    // 選擇在行 r 放子
    for (int c = 0; c < n; ++c)
        if (!col[c] && g[r][c] == '#') {
            col[c] = 1;
            dfs(r+1, cnt+1);
            col[c] = 0;
        }
    // 選擇不放
    dfs(r+1, cnt);
}

int main() {
    while (scanf("%d%d", &n, &k) == 2 && n != -1) {
        for (int i=0; i