POJ 1753 Flip Game：4×4 棋盤最少翻轉步數（DFS + 剪枝）

問題規則

• 4×4 棋盤，每格黑(b)或白(w)。
• 一次操作選一格，翻轉該格及其上下左右相鄰格（共 3~5 格）。
• 目標：全白或全黑。求最少步數，不可行輸出 Impossible。

狀態空間極小

共 2¹⁶ = 65536 種狀態，可用 **IDA\*** 或 **帶步數限制的 DFS** 暴力搜索。

DFS + 迭代加深

• 按行優先順序枚舉是否翻轉當前格。
• 當前步數達到限制 step 時檢查是否達標。
• 從 step = 0 遞增到 16，首次成功即為最小步數。
• 翻轉操作可逆，回溯時再翻一次即可恢復。

代碼實現

#include <bits/stdc++.h>
using namespace std;

int board[5][5];
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
int limit, found;

bool check() {
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
            if (board[i][j] != board[1][1]) return false;
    return true;
}

void flip(int x, int y) {
    for (int d = 0; d < 5; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx >= 1 && nx <= 4 && ny >= 1 && ny <= 4)
            board[nx][ny] ^= 1;
    }
}

void dfs(int x, int y, int depth) {
    if (found) return;
    if (depth == limit) {
        if (check()) found = true;
        return;
    }
    if (x > 4) return;

    // 選擇翻轉 (x,y)
    flip(x, y);
    int nx = (y == 4) ? x + 1 : x;
    int ny = (y == 4) ? 1 : y + 1;
    dfs(nx, ny, depth + 1);
    flip(x, y); // 回溯

    // 不翻轉
    dfs(nx, ny, depth);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    char ch;
    for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
            cin >> ch;
            board[i][j] = (ch == 'b');
        }
    }
    for (limit = 0; limit <= 16; ++limit) {
        found = false;
        dfs(1, 1, 0);
        if (found) break;
    }
    if (found) cout << limit << '\n';
    else cout << "Impossible\n";
    return 0;
}

優化提示

可用位掩碼（16 位整數）表示狀態，BFS 預計算所有到全 0/全 1 的距離，多測試用例極快。但單測 DFS 迭代加深已足夠（<1ms）。