POJ 1222 EXTENDED LIGHTS OUT：高斯消元法解開關燈謎題

題目大意

5×6 矩陣按鈕，每個按鈕控制自身及上下左右鄰居（邊角少一個）的燈狀態翻轉（0↔1）。給定初始亮燈狀態，求按下哪些按鈕（每個最多按一次）可使所有燈熄滅。輸出按鈕按下方案（1=按，0=不按）。

數學建模

設 x[i][j] ∈ {0,1} 表示按鈕 (i,j) 是否按下。每個燈最終狀態為初始狀態加上影響它的所有按鈕操作（模 2 加，即 XOR）。對於燈 (i,j)：

初始[i][j] + x[i][j] + x[i-1][j] + x[i+1][j] + x[i][j-1] + x[i][j+1] ≡ 0 (mod 2)

移項得 30 元一次方程組（模 2 意義下）。係數矩陣 A 為 30×30，A[p][q]=1 若按鈕 q 影響燈 p。右端向量 b 為初始狀態。解 A·x = b (mod 2)。

高斯消元 (模 2)

• 模 2 下加法 = 減法 = XOR（^）。
• 主元為 1 時無需除法，直接消元。
• 若主元為 0，向下尋找非零行交換。
• 消元後直接得解（題目保證唯一解）。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int N = 30;
int a[N][N+1]; // 增廣矩陣

void gauss() {
    for (int col = 0, row = 0; col < N; ++col) {
        int sel = row;
        while (sel < N && !a[sel][col]) ++sel;
        if (sel == N) continue; // 本題不會發生
        if (sel != row) for (int j = col; j <= N; ++j) swap(a[sel][j], a[row][j]);
        for (int i = 0; i < N; ++i)
            if (i != row && a[i][col])
                for (int j = col; j <= N; ++j)
                    a[i][j] ^= a[row][j];
        ++row;
    }
}

int main() {
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        memset(a, 0, sizeof(a));
        // 讀入初始狀態到增廣列
        for (int i = 0; i < N; ++i) cin >> a[i][N];
        // 構造係數矩陣
        for (int i = 0; i < N; ++i) {
            int r = i / 6, c = i % 6;
            for (int j = 0; j < N; ++j) {
                int r2 = j / 6, c2 = j % 6;
                if (abs(r-r2) + abs(c-c2) <= 1) a[i][j] = 1;
            }
        }
        gauss();
        cout << "PUZZLE #" << tc << '\n';
        for (int i = 0; i < N; ++i) {
            if (i) cout << ' ';
            cout << a[i][N];
            if ((i+1) % 6 == 0) cout << '\n';
        }
    }
    return 0;
}

關鍵點

• 按鈕順序無關，每個按鈕最多按一次（按兩次抵消）。
• 模 2 高斯消元僅需 XOR 操作，極其高效。
• 係數矩陣固定，可預計算逆矩陣，但現場消元 30×30 瞬間完成。