問題描述

R×C 面板（R,C ≤ ?），初始全暗。按下某燈會翻轉自身及鄰近燈（根據給定 3×3 模式）。求最少按幾下使全亮，輸出按鈕編號（1-based，行優先）。無解輸出 Impossible。

關鍵觀察

• 操作可交換、冪等（按兩次等於不按），每個燈只需考慮按 0/1 次。
• 按鈕影響範圍局限於 3×3 區域，第 i 行燈僅受第 i-1, i, i+1 行按鈕影響。
• 逐行決定法：第一行按鈕任意枚舉（2^C 種），第二行按鈕由第一行狀態唯一決定（為使第一行全亮），以此類推。最後檢查最後一行是否全亮。

但本題採用全局 DFS + 剪枝：狀態壓縮為位掩碼，按鈕預計算影響掩碼，DFS 遍歷所有按鈕組合（最多 2^(R*C)），剪枝：若處理到第 r 行，第 r-2 行仍有暗燈 → 剪枝（因後續按鈕無法影響第 r-2 行）。

狀態壓縮與預計算

int R, C;
long long effect[30]; // effect[i] = 按鈕 i 影響的燈位掩碼
int target; // 全亮掩碼 = (1<<(R*C))-1

void init() {
    // 讀取 3x3 模式，記錄相對偏移
    // 對每個按鈕 (r,c)，計算其影響的絕對位置，設置 effect[idx] 對應位
}

DFS + 剪枝

int best = INF;
int press[30]; // 當前按鈕選擇
int best_press[30];

void dfs(int idx, long long state, int cnt) {
    if (state == target) { // 全亮
        if (cnt < best) { best = cnt; memcpy(best_press, press, sizeof(press)); }
        return;
    }
    if (idx == R*C) return;
    
    // 剪枝：檢查 idx 所在行的上上行是否全亮
    int r = idx / C;
    if (r >= 2) {
        int check_row = r - 2;
        long long row_mask = 0;
        for (int c=0;c

完整代碼結構
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXRC = 30;
long long effect[MAXRC];
int press[MAXRC], best_press[MAXRC];
int R, C, best;
long long target;

void init_effect() {
    char pat[3][4];
    for (int i=0;i<3;++i) scanf("%s", pat[i]);
    int dr[9], dc[9], cnt=0;
    for (int i=0;i<3;++i)
        for (int j=0;j<3;++j)
            if (pat[i][j]=='*') { dr[cnt]=i-1; dc[cnt]=j-1; ++cnt; }
    
    memset(effect, 0, sizeof(effect));
    for (int r=0;r=0 && nr=0 && nc= 2) {
        int cr = r-2;
        long long mask = 0;
        for (int c=0;c R*C) puts("Impossible.");
        else {
            bool first = true;
            for (int i=0;i

關鍵細節

位掩碼用 long long：R*C 可能達 30，1LL<<30 安全。
剪枝條件：處理到第 r 行按鈕時，第 r-2 行燈狀態已定（後續按鈕最多影響 r-1 行），必須全亮。
按鈕編號輸出：1-based，行優先，空格分隔。
多測試用例：直到 EOF。


複雜度

最坏 2^(R*C)，但剪枝極其有效，實際搜索節點極少。
R,C ≤ 5 典型情況下瞬間出解。


總結
UVA 10318 是「燈泡開關 + 狀態壓縮 DFS + 剪枝」經典題。核心技巧：

預計算每個按鈕的影響掩碼，狀態轉移為 XOR。
利用「影響範圍局限性」設計剪枝：第 r-2 行狀態不可逆。
全局 DFS 枚舉按/不按，記錄最優解。

此模板適用於所有「局部操作影響局部區域、操作可交換冪等、求最小操作數」問題（如 Lights Out 變體）。