南京理工大學 OJ 1014：區域監控攝像頭最大安裝數回溯法解題

問題建模與回溯剪枝

將區域抽象為 n×n 網格（n≤4），牆壁阻擋視線，攝像頭覆蓋所在行列直至牆壁。求最大非衝突安裝數。

回溯核心邏輯

• 按單元格線性索引 m = 0..n*n-1 遞歸嘗試放置/不放置。
• CanPlace(m)：檢查同行同列（直至牆壁）是否已有攝像頭。
• 葉節點統計當前放置數，更新全局最大值。

關鍵剪枝

bool CanPlace(int m) {
    int r = m / n, c = m % n;
    if (grid[r][c] == WALL) return false;
    // 向上/向左掃描至牆壁或邊界
    for (int i = r-1; i >= 0; --i) {
        if (grid[i][c] == WALL) break;
        if (place[i][c]) return false;
    }
    for (int j = c-1; j >= 0; --j) {
        if (grid[r][j] == WALL) break;
        if (place[r][j]) return false;
    }
    return true;
}

複雜度

n≤4 時狀態空間 2^16=65536，回溯極快，無需進一步優化。

樣例驗證

• 4×4 全空 → 最大 4（對角線放置）。
• 含牆壁 → 最大 5（利用牆壁分隔行列視線）。