您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 1753 Flip Game：高斯消元解 4×4 翻棋遊戲

編輯：C++ 入門

POJ 1753 Flip Game：高斯消元解 4×4 翻棋遊戲

4×4 棋盤，每格黑/白。操作：選一格，翻轉它及其上下左右相鄰格。目標：全白或全黑。求最少步數，無解輸出 "Impossible"。

GF(2) 線性方程組建模

16 個變數 x_0..x_15 ∈ {0,1} 表示是否操作該格。
每格最終顏色 = 初始顏色 + 自身操作 + 四鄰域操作 (mod 2)。
目標全白：最終顏色 = 0；目標全黑：最終顏色 = 1。建立兩組方程組分別求解，取較小步數。

高斯消元 + 自由變元枚舉

16 元 16 方程，消元後可能有自由變元。枚舉自由變元的 0/1 組合（最多 2^4=16 種），回代得特解，統計 1 的個數（操作次數），取最小值。

關鍵程式碼片段 (C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 16;
int a[N][N+1], x[N];
int gauss(int target) { // target=0 全白, 1 全黑
    memset(a, 0, sizeof(a));
    // 建立係數矩陣：每格影響自身及四鄰域
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j) {
            int id = i*4 + j;
            a[id][id] = 1;
            if (i) a[id][(i-1)*4+j] = 1;
            if (i<3) a[id][(i+1)*4+j] = 1;
            if (j) a[id][i*4+j-1] = 1;
            if (j<3) a[id][i*4+j+1] = 1;
        }
    // 讀入初始狀態，構建常數項
    char s[5];
    for (int i = 0; i < 4; ++i) {
        cin >> s;
        for (int j = 0; j < 4; ++j)
            a[i*4+j][N] = (s[j] == 'b') ^ target; // 目標全白: b->1需翻; 目標全黑: w->1需翻
    }
    // 高斯消元 (GF(2))
    int row = 0;
    for (int col = 0; col < N && row < N; ++col) {
        int sel = row;
        while (sel < N && !a[sel][col]) ++sel;
        if (sel == N) continue;
        swap(a[sel], a[row]);
        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;
    }
    // 檢查無解
    for (int i = row; i < N; ++i) if (a[i][N]) return -1;
    // 自由變元枚舉 (N-row 個)
    int freeVar = N - row;
    int ans = N+1;
    for (int mask = 0; mask < (1 << freeVar); ++mask) {
        memset(x, 0, sizeof(x));
        // 將自由變元賦值（對應行）
        for (int i = 0; i < freeVar; ++i)
            x[row + i] = (mask >> i) & 1;
        // 回代
        for (int i = row - 1; i >= 0; --i) {
            int col = 0;
            while (col < N && !a[i][col]) ++col;
            int sum = a[i][N];
            for (int j = col + 1; j < N; ++j) sum ^= a[i][j] & x[j];
            x[col] = sum;
        }
        int cnt = 0;
        for (int i = 0; i < N; ++i) cnt += x[i];
        ans = min(ans, cnt);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    char s[5];
    while (cin >> s[0]) {
        for (int i = 1; i < 4; ++i) cin >> s[i];
        int ans1 = gauss(0), ans2 = gauss(1);
        if (ans1 == -1 && ans2 == -1) cout << "Impossible\n";
        else if (ans1 == -1) cout << ans2 << '\n';
        else if (ans2 == -1) cout << ans1 << '\n';
        else cout << min(ans1, ans2) << '\n';
    }
    return 0;
}