POJ 1222 EXTENDED LIGHTS OUT：高斯消元解異或線性方程組

問題描述

5×6 燈板，初始全滅。按下某燈會翻轉該燈及其上下左右四鄰居（共 5 燈，邊角少）。給定目標亮燈模式，求按燈方案（輸出 0/1 矩陣）。多組測試。

數學建模

• 30 盞燈 → 30 個 0/1 變量 x_0..x_29（1 表示按下）。
• 每盞燈最終狀態 = 初始狀態 (0) + 影響它的變量異或和 = 目標狀態。
• 得到 30 元 30 方程：A * x = b（模 2 意義下，即 GF(2) 線性方程組）。
• 係數矩陣 A[30][30]：A[i][j] = 1 若按燈 j 影響燈 i，否則 0。
• 增廣矩陣 [A | b] 30×31。

高斯消元（GF(2)）

• 列主元消元：對每列 col，找 row ≥ col 使 A[row][col] = 1，交換行。
• 對下方行 i > row，若 A[i][col] = 1，則 A[i] ^= A[row]（整行異或）。
• 回代：從最後一行向上，x[i] = b[i] ^ Σ(A[i][j] & x[j])。
• GF(2) 下加減法均為異或，乘法為與，無除法問題。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int A[N][N+1], init[N][N+1];
int ans[N];
int dx[5] = {0,1,0,-1,0}, dy[5] = {0,0,1,0,-1};

int gauss() {
    memcpy(A, init, sizeof(init));
    int row = 0;
    for (int col = 0; col < N; ++col) {
        int sel = row;
        while (sel < N && A[sel][col] == 0) ++sel;
        if (sel == N) continue;
        if (sel != row) swap(A[sel], A[row]);
        for (int i = row + 1; i < N; ++i)
            if (A[i][col])
                for (int j = col; j <= N; ++j)
                    A[i][j] ^= A[row][j];
        ++row;
    }
    // 回代
    for (int i = N - 1; i >= 0; --i) {
        int col = -1;
        for (int j = 0; j < N; ++j) if (A[i][j]) { col = j; break; }
        if (col == -1) {
            if (A[i][N]) return 0;  // 0 = 1 無解
            continue;
        }
        ans[col] = A[i][N];
        for (int j = col + 1; j < N; ++j)
            if (A[i][j]) ans[col] ^= ans[j];
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 預構造係數矩陣 init
    memset(init, 0, sizeof(init));
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 6; ++j) {
            int id = i * 6 + j;
            for (int d = 0; d < 5; ++d) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni >= 0 && ni < 5 && nj >= 0 && nj < 6)
                    init[id][ni * 6 + nj] = 1;
            }
        }
    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        for (int i = 0; i < 5; ++i)
            for (int j = 0; j < 6; ++j) {
                int v; cin >> v;
                A[i*6+j][N] = v;
            }
        gauss();
        cout << "PUZZLE #" << cas << '\n';
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 6; ++j) {
                cout << ans[i*6+j] << (j==5?'\n':' ');
            }
        }
    }
    return 0;
}

複雜度

固定 30 變量，高斯消元 O(30^3) ≈ 2.7×10⁴ 操作/測試用例，極快。

關鍵點

1. GF(2) 線性方程組，異或消元。
2. 預構造係數矩陣，每組只填充增廣列。
3. 輸出格式：每行 6 個數，空格分隔，行末換行。