POJ 1222 EXTENDED LIGHTS OUT：高斯消元法解燈燈滅遊戲（0-1 矩陣）

POJ 1222 EXTENDED LIGHTS OUT：高斯消元法解燈燈滅遊戲（0-1 矩陣）

5×6 棋盤，每盞燈狀態 0/1。操作某燈會翻轉自身及上下左右四鄰居。求操作矩陣使所有燈熄滅。經典「Lights Out」遊戲，本質是 GF(2) 域上線性方程組 A·x = b，高斯消元求解。

數學建模

• 30 盞燈編號 0~29，x[i]=1 表示操作第 i 燈，b[i] 為初始狀態。
• 操作矩陣 A[30][30]：A[i][j]=1 表示操作燈 j 影響燈 i。對稱矩陣，對角線為 1（自身），相鄰為 1。
• 方程：Σ A[i][j]·x[j] ≡ b[i] (mod 2)，即異或運算。

增廣矩陣構造

void init() {
    for (int i = 0; i < 5; i++) for (int j = 0; j < 6; j++) {
        int x = i*6 + j; A[x][x] = 1; // 自身
        for (int k = 0; k < 4; k++) { // 四鄰居
            int ni = i + di[k], nj = j + dj[k];
            if (ni>=0 && ni<5 && nj>=0 && nj<6)
                A[ni*6+nj][x] = 1; // 注意：列向量表示操作影響
        }
    }
}

增廣矩陣最後一列存 b[i]（初始狀態）。

GF(2) 高斯消元

int Gauss() {
    for (int i = 0; i < 30; i++) {
        int mx = i;
        for (int j = i+1; j < 30; j++) if (abs(A[j][i]) > abs(A[mx][i])) mx = j;
        if (A[mx][i] == 0) { free_var++; continue; } // 自由變元
        if (mx != i) for (int k = i; k <= 30; k++) swap(A[i][k], A[mx][k]);
        for (int j = i+1; j < 30; j++)
            if (A[j][i]) for (int k = i; k <= 30; k++) A[j][k] ^= A[i][k]; // 異或消元
    }
    if (free_var) return free_var; // 多解
    for (int i = 29; i >= 0; i--) {
        x[i] = A[i][30];
        for (int j = i+1; j < 30; j++) x[i] ^= (A[i][j] && x[j]); // 回代
    }
    return 0;
}

關鍵點：^= 實現模 2 減法，&& 配合 ^= 實現模 2 乘加。列主元選擇非零行（GF(2) 下絕對值即非零判斷）。

輸出格式

每行 6 個數，空格分隔，換行。多組測試用例循環處理。

複雜度與通用性

• O(n³) = 30³ = 27,000 操作，極快。
• 模板可直接擴展至任意 m×n 棋盤、任意鄰域定義、帶權重版本。

總結

「燈燈滅」是 0-1 線性代數在遊戲中的完美應用。將操作影響關係建模為 GF(2) 矩陣，高斯消元一氣呵成。掌握「問題→線性方程組→增廣矩陣→消元→回代」建模鏈路，是解決翻轉遊戲、電路分析、編碼理論等問題的核心技能。