HDU 4012 Paint on a Wall - 2×N 棋盤最少矩形染色步數 BFS 狀態壓縮

題目大意

2×N (N≤8) 棋盤，每格大寫字母表示顏色。刷子可一次染一個矩形區域為單一顏色（覆蓋舊色）。求從空白棋盤達到目標圖案的最少步數。

狀態壓縮 BFS

• 狀態編碼：每行 N 格，每格 4 位（最多 16 色），兩行共 2N×4 ≤ 64 位，用 uint64_t 壓縮。
• 初始狀態：全 0（空白）。
• 目標狀態：輸入圖案編碼。
• 擴展動作：枚舉所有矩形 (r1,c1)-(r2,c2) 及所有出現過的顏色，生成新狀態。N≤8，矩形數 O(N⁴) ≈ 4096，顏色 ≤ 26，總分支可控。
• 去重：unordered_set 或 vector (2^16=65536 狀態空間極小，可用數組)。

關鍵代碼 (C++)

#include 
using namespace std;

using ULL = unsigned long long;
int N, T;
ULL encode(const vector& g) { /* 2行N列，每格4位壓入ULL */ }
vector decode(ULL s) { /* 反向解碼，用於調試 */ }

int main() {
    cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        cin >> N;
        vector target(2);
        cin >> target[0] >> target[1];
        ULL goal = encode(target);

        queue> q;
        unordered_set vis;
        q.emplace(0, 0); // 空白狀態
        vis.insert(0);

        int ans = -1;
        while (!q.empty()) {
            auto [state, dist] = q.front(); q.pop();
            if (state == goal) { ans = dist; break; }

            // 解碼為 2xN 顏色數組 (0=空白, 1..26=顏色)
            int color[2][8];
            ULL tmp = state;
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < N; ++j) {
                    color[i][j] = tmp & 0xF;
                    tmp >>= 4;
                }

            // 枚舉所有矩形
            for (int r1 = 0; r1 < 2; ++r1)
                for (int c1 = 0; c1 < N; ++c1)
                    for (int r2 = r1; r2 < 2; ++r2)
                        for (int c2 = c1; c2 < N; ++c2) {
                            // 該矩形內已有的顏色集合（只需嘗試這些顏色+目標顏色）
                            bool used[27] = {};
                            for (int i = r1; i <= r2; ++i)
                                for (int j = c1; j <= c2; ++j)
                                    if (color[i][j]) used[color[i][j]] = true;
                            // 為了收斂，優先嘗試目標矩形區域的顏色
                            for (int col = 1; col <= 26; ++col) if (used[col]) {
                                ULL nstate = state;
                                for (int i = r1; i <= r2; ++i)
                                    for (int j = c1; j <= c2; ++j) {
                                        int pos = (i*N + j) * 4;
                                        nstate = (nstate & ~(0xFULL << pos)) | (ULL(col) << pos);
                                    }
                                if (vis.insert(nstate).second)
                                    q.emplace(nstate, dist + 1);
                            }
                        }
        }
        cout << "Case #" << tc << ": " << ans << '\n';
    }
    return 0;
}

優化技巧

• 只嘗試目標顏色：矩形染色若不匹配目標顏色通常無意義，大幅減少分支。
• 雙向 BFS：從目標狀態反向搜索（反向操作：將矩形區域改為任意顏色），相遇時合併步數。
• A* / IDA*：啟發函數 = 未匹配格子數 / 矩形最大面積。

總結

本題狀態空間極小 (2^(4·2N) ≤ 2^64 但實際可達狀態很少)，BFS + 狀態壓縮是標準解。關鍵在於高效的編碼/解碼、矩形枚舉、去重。N≤8 保證在時限內跑完。面試中能說清壓縮方案、BFS 框架、剪枝思路即可。