UVA 10318 Security Panel - DFS 剪枝解法詳解

題目背景

這是一個經典的「開關燈」變體問題。給定一個 r × c 的面板，初始全關。每個開關按下會根據預設的 3×3 模式翻轉特定位置的燈的狀態。目標是找出從全關變全開的最少按鍵步數，並輸出按鍵序列（按行優先、列次之的編碼）。若無解輸出 "Impossible."。

核心觀察與剪枝策略

1. 按鍵冪等性

同一位置按兩次等於不按，因此每個位置只有「按」或「不按」兩種選擇，搜索空間為 2^(r×c)。

2. 影響範圍局限性

開關影響範圍為 3×3，故某行的狀態僅受該行及上一行按鍵影響。當決定完第 i 行的按鍵後，第 i-1 行的燈狀態已完全確定，不可再改變。因此在遞歸進入下一行前，必須檢查上上行（i-2）是否全亮——這是關鍵剪枝點。

3. 狀態回溯

使用 pressfunc(x, y) 執行按鍵操作（翻轉受影響的燈），遞歸返回前再次調用以復原狀態，實現原地回溯，無需複製整個面板。

算法流程

1. 讀取測試用例，解析 3×3 影響模式
2. 初始化面板全為 0（關），設置答案上界 cnt = r*c + 1
3. 從 (0,0) 開始 DFS：
• 若列越界，檢查終止條件或換行
• 嘗試「不按」遞歸
• 嘗試「按下」：執行操作、記錄步驟、遞歸、復原操作
4. 若找到更優解，更新答案序列
5. 輸出結果

代碼關鍵片段

bool check(int l1) { // 檢查第 l1 行是否全亮
    if (l1 >= 0) {
        for (int i = 0; i < c; i++)
            if (!lit[l1][i]) return false;
    }
    return true;
}

void dfs(int x, int y, int press) {
    if (y == c) { // 換行處理
        if (x == r - 1) { // 最後一行，檢查全部
            for (int i = 0; i < r; i++) if (!check(i)) return;
            if (press < cnt) { /* 更新答案 */ }
            return;
        } else {
            if (!check(x - 2)) return; // 關鍵剪枝：上上行必須全亮
            x++; y = 0;
        }
    }
    dfs(x, y + 1, press);        // 不按
    pressfunc(x, y);
    prs[press] = c * x + y + 1;  // 記錄按鍵編碼
    dfs(x, y + 1, press + 1);    // 按下
    pressfunc(x, y);             // 復原
}

複雜度分析

最壞情況 O(2^(r×c))，但得益於「上上行必須全亮」的強力剪枝，實際運行極快。數據規模較小（r, c ≤ 5），完全在時限內。

總結

本題展示了在局部影響範圍問題中，利用「狀態確定性」進行逐行決策與剪枝的經典技巧。關鍵在於識別出「哪一行的狀態已不可逆」，並在此時刻進行檢查，大幅壓縮搜索空間。