POJ 1753 Flip Game - 位運算 + BFS 求最少翻轉步數

問題描述

在一個 4×4 的棋盤上，每個格子有一面黑、一面白的棋子。每次操作選擇一個格子，翻轉該格子及其上下左右相鄰的格子（共 3~5 個）。目標是使所有棋子同色（全白或全黑）。求從給定初始狀態達到目標的最少操作步數，若不可能則輸出 "Impossible"。

位運算狀態壓縮

4×4 = 16 格，用一個 16 位整數表示狀態：第 i 位為 1 代表黑，0 代表白。總狀態數 2^16 = 65536，適合 BFS。

翻轉第 i 格（0-indexed）的操作：state ^= (1 << i)；同時翻轉相鄰格子（上 i-4、下 i+4、左 i-1、右 i+1，需判斷邊界）。預先計算 16 個操作對應的掩碼 flipMask[16]，則新狀態 newState = state ^ flipMask[i]。

BFS 搜索

從初始狀態開始 BFS，目標狀態為 0 (全白) 或 65535 (全黑)。訪問數組 vis[65536] 記錄是否入隊。每個狀態嘗試 16 種操作，未訪問過則入隊。找到目標輸出步數，隊列為空則輸出 "Impossible"。

複雜度

狀態數 65536，每狀態 16 操作，總操作 ~10^6，時間記憶體均符合限制。

參考代碼 (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

bool vis[1<<16];
int flipMask[16];

struct Node { int state, step; };

void initMasks() {
    for (int i = 0; i < 16; ++i) {
        int mask = 1 << i;           // 自身
        if (i >= 4)   mask |= 1 << (i-4); // 上
        if (i < 12)   mask |= 1 << (i+4); // 下
        if (i % 4)    mask |= 1 << (i-1); // 左
        if ((i+1)%4)  mask |= 1 << (i+1); // 右
        flipMask[i] = mask;
    }
}

int bfs(int start) {
    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    q.push({start, 0});
    vis[start] = true;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.state == 0 || cur.state == 65535) return cur.step;
        for (int i = 0; i < 16; ++i) {
            int ns = cur.state ^ flipMask[i];
            if (!vis[ns]) {
                vis[ns] = true;
                q.push({ns, cur.step + 1});
            }
        }
    }
    return -1; // Impossible
}

int main() {
    initMasks();
    char ch;
    int start = 0;
    for (int i = 0; i < 16; ++i) {
        cin >> ch;
        if (ch == 'b') start |= 1 << i;
    }
    int ans = bfs(start);
    if (ans >= 0) cout << ans << endl;
    else cout << "Impossible" << endl;
    return 0;
}