ZOJ 1002 Fire Net：DFS 回溯求最大放置炮台數

問題描述

n×n 棋盤（n≤4），部分格子為牆（'X'）。炮台可放置於空格（'.'），同行同列不可互相攻擊（中間無牆阻隔）。求最大放置數。

DFS 回溯解法

int n, max, count, target[4][4];

int place(int x, int y) { // 檢查 (x,y) 能否放置
    for (int i=y; i>=0; i--) { if (target[x][i]>0) return 0; if (target[x][i]<0) break; }
    for (int i=y; i0) return 0; if (target[x][i]<0) break; }
    for (int i=x; i>=0; i--) { if (target[i][y]>0) return 0; if (target[i][y]<0) break; }
    for (int i=x; i0) return 0; if (target[i][y]<0) break; }
    return 1;
}

void DFS() {
    if (count > max) max = count;
    for (int i=0; i
關鍵點

place() 向四方向掃描，遇牆停止，遇炮台返回失敗。
DFS() 遍歷所有格子，嘗試放置並遞歸，回溯時恢復狀態。
n≤4，狀態空間極小，暴力回溯完全可行。

常見錯誤

未處理多組測試數據輸入結束條件。
掃描方向邊界條件寫錯導致越界或漏判。