問題描述

N×N 城市地圖（N≤4），'.' 空地，'X' 牆。放置堡壘，每個堡壘四面射擊（上下左右），子彈穿透空地被牆阻擋。任意兩堡壘不可互相射擊（即同行/同列無牆阻隔時不可共存）。求最大放置數。

DFS 回溯 + 剪枝

• N≤4 → 格子數 ≤ 16，暴力枚舉所有子集 2^16 = 65536 完全可行。
• 按位置序 0..N²-1 遞歸：每格選「放」或「不放」。
• 合法性檢查：向上/向左掃描至牆或邊界，若遇堡壘則不合法。
• 全局記錄最大值。

代碼實現

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

char mp[10][10];
int N, ans;

bool can_place(int r, int c) {
    // 向上
    for (int i=r-1; i>=0; --i) {
        if (mp[i][c]=='X') break;
        if (mp[i][c]=='B') return false;
    }
    // 向左
    for (int j=c-1; j>=0; --j) {
        if (mp[r][j]=='X') break;
        if (mp[r][j]=='B') return false;
    }
    return true;
}

void dfs(int pos, int cnt) {
    if (pos == N*N) { ans = max(ans, cnt); return; }
    int r = pos/N, c = pos%N;
    if (mp[r][c] == '.') {
        if (can_place(r,c)) {
            mp[r][c] = 'B';
            dfs(pos+1, cnt+1);
            mp[r][c] = '.';
        }
    }
    dfs(pos+1, cnt); // 不放
}

int main() {
    while (~scanf("%d", &N) && N) {
        for (int i=0;i

關鍵細節

掃描方向：只需向上、向左檢查，因 DFS 按行優先順序，右/下方尚未放置堡壘。
牆阻隔：遇到 'X' 即停止掃描，牆後堡壘不構成威脅。
字符標記：用 'B' 表示堡壘，回溯時恢復 '.'。
多測試用例：以 0 結束。


複雜度

最多 2^16 狀態，每狀態合法性檢查 O(N) ≤ 4，總操作 < 100萬，瞬間出解。


總結
NYOJ 587 是小規模 DFS 回溯的典型應用。N≤4 使得狀態空間極小，無需複雜剪枝或狀態壓縮 DP。關鍵在於：

按固定順序枚舉決策（放/不放）。
利用已放置信息的局部性（只需檢查上/左）快速判斷合法性。
回溯時恢復現場。

此「暴力枚舉 + 增量合法性檢查」模板適用於所有小規模「放置/選擇 + 相互約束」問題（如 N 皇后、數獨、最大獨立集）。