POJ 1222：5×6 矩陣翻轉遊戲的高斯消元解法

問題背景

經典的「關燈遊戲」變體：給定一個 5 行 6 列的矩陣，每個位置代表一個按鈕及燈。按下按鈕會翻轉自身及上下左右四個鄰居的狀態（0↔1）。求一組按鈕操作，使所有燈熄滅（全 0）。輸出同樣大小的矩陣，1 表示按下，0 表示不按。

數學建模

設變量 x[i][j] ∈ {0,1} 表示是否按下第 (i,j) 個按鈕。每個燈的最終狀態由初始狀態加上受影響的按鈕操作模 2 決定。這構成一個模 2 的線性方程組：

A * X = B   (mod 2)

其中 A 是 30×30 的係數矩陣，X 是 30 維未知向量，B 是初始狀態向量。因為模 2 下加法即 XOR，高斯消元極其適合。

高斯消元步驟 (模 2)

1. 構建增廣矩陣 aug[30][31]，最後一列為常數項。
2. 列主元消元：對每一列，尋找非零行交換到當前行，然後將下方行消零（XOR 操作）。
3. 回代求解：從最後一行向上，確定每個變量值。
4. 若有自由變量，題目保證有解，取任一解即可（通常自由變量設 0）。

關鍵代碼片段

const int N = 30;
int aug[N][N+1], x[N];
int dx[5] = {0,0,1,0,-1};
int dy[5] = {0,1,0,-1,0};

void build_matrix() {
    memset(aug, 0, sizeof(aug));
    for (int i=0;i<5;i++)
        for (int j=0;j<6;j++) {
            int id = i*6 + j;
            for (int k=0;k<5;k++) {
                int ni = i + dx[k], nj = j + dy[k];
                if (ni>=0 && ni<5 && nj>=0 && nj<6)
                    aug[id][ni*6+nj] = 1;
            }
            aug[id][N] = initial_state[i][j]; // 常數項
        }
}

int gauss() {
    int row=0, col=0;
    for (; row<N && col<N; row++, col++) {
        int sel = row;
        for (int i=row;i<N;i++) if (aug[i][col]) { sel=i; break; }
        if (!aug[sel][col]) { row--; continue; }
        if (sel != row) for (int j=col;j<=N;j++) swap(aug[sel][j], aug[row][j]);
        for (int i=0;i<N;i++) if (i!=row && aug[i][col])
            for (int j=col;j<=N;j++) aug[i][j] ^= aug[row][j];
    }
    for (int i=0;i<N;i++) x[i] = aug[i][N];
    return 0;
}

輸出格式

將解向量 x 重組為 5×6 矩陣，每行空格分隔，行間換行。題目要求每組數據前輸出 PUZZLE #k。

總結

POJ 1222 是高斯消元在模 2 線性系統中應用的教科書級例題。關鍵在於正確建立係數矩陣，並利用位運算（XOR）高效實現消元。掌握此模板，可解決大量「翻轉/開關」類問題。