HDU Flood-it! - IDA* 求最少染色步數

題目大意

N×N (2≤N≤8) 棋盤，每格顏色 0~5。從左上角 (0,0) 開始，每步選一種顏色，將與起點連通區域（四連通、同色）整體改為該顏色，從而吞併相鄰同色區域。求將全棋盤變為單一顏色的最少步數。

IDA* 核心設計

• 狀態：當前棋盤顏色矩陣。但完整矩陣太大，實際只需維護「與左上角連通區域」的掩碼。
• 連通區域擴展：DFS/BFS 從 (0,0) 擴展，標記 vis=1（已連通）、vis=2（相鄰不同色，下一步可吞併）。
• 啟發函數 h：統計 vis==2 的不同顏色數。因為每步只能消除一種邊界顏色，至少還需該數步。這是可接受的（不超估）。
• 剪枝：depth + h > limit 回溯；不嘗試與當前連通區顏色相同的顏色（無效步）；可選：按邊界顏色出現頻率排序優先嘗試。
• 迭代加深：limit = h(initial) 開始遞增，直到找到解。

關鍵代碼 (C++)

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

int N, limit;
int board[8][8];
int vis[8][8];      // 0=未訪問, 1=連通區, 2=邊界不同色
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void dfs_mark(int x, int y, int color) {
    if (x<0||x>=N||y<0||y>=N) return;
    if (vis[x][y]) return;
    if (board[x][y] == color) {
        vis[x][y] = 1;
        for (auto &d: dirs) dfs_mark(x+d[0], y+d[1], color);
    } else {
        vis[x][y] = 2; // 邊界不同色
    }
}

int heuristic() {
    bool hasColor[6] = {false};
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (vis[i][j] == 2)
                hasColor[board[i][j]] = true;
    int cnt = 0;
    for (int c = 0; c < 6; ++c) if (hasColor[c]) ++cnt;
    return cnt;
}

bool IDA(int depth) {
    int h = heuristic();
    if (h == 0) return true;
    if (depth + h > limit) return false;

    int curColor = board[0][0];
    // 保存現場
    int backupVis[8][8];
    memcpy(backupVis, vis, sizeof(vis));

    for (int c = 0; c < 6; ++c) {
        if (c == curColor) continue; // 跳過同色
        // 模擬染色 c：將所有 vis==1 改為 c，然後重新標記
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (vis[i][j] == 1) board[i][j] = c;

        memset(vis, 0, sizeof(vis));
        dfs_mark(0, 0, c);

        if (IDA(depth + 1)) return true;

        // 回溯恢復
        memcpy(vis, backupVis, sizeof(vis));
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (backupVis[i][j] == 1) board[i][j] = curColor;
    }
    return false;
}

int main() {
    while (cin >> N, N) {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                cin >> board[i][j];

        memset(vis, 0, sizeof(vis));
        dfs_mark(0, 0, board[0][0]);

        for (limit = heuristic(); ; ++limit) {
            if (IDA(0)) break;
        }
        cout << limit << '\n';
    }
    return 0;
}

優化技巧

• 狀態壓縮：用 64 位整數編碼棋盤（每格 3 位，6 色），配合哈希表去重（雖 IDA* 通常不存 visited，但可加 transposition table）。
• 顏色排序：優先嘗試邊界區域面積最大的顏色，往往能更快收斂。
• 對稱性剪枝：若連續兩步染同一顏色無意義，可記錄上一步顏色避免重複。

總結

Flood-it 是 IDA* 經典應用：狀態隱含在連通區擴展中，啟發函數取「邊界不同色數」既簡單又有效。N≤8 保證搜尋深度極淺（通常 ≤ 10 步），迭代加深極快。關鍵在於正確實現「染色 → 重新連通標記 → 遞歸 → 回溯」的流程。