HDU 4127 Flood - Flood-it 遊戲 IDA* 求最少步數

題目大意

同 HDU Flood-it!，N×N (N≤8) 棋盤，6 種顏色，從左上角連通區擴展，求全板同色最少步數。多測試用例，N=0 結束。

IDA* 實現細節

• 連通區標記：DFS 從 (0,0) 擴展，vis=1 連通區，vis=2 邊界不同色。
• 啟發函數：統計 vis==2 的不同顏色數 cnt。每步最多消除一種邊界顏色，故 h = cnt 為可接受下界。
• 染色操作：選顏色 c (0~5, ≠ 當前色)，將所有 vis==1 改為 c，重新 DFS 標記。
• 回溯恢復：用備份數組恢復 board 和 vis。
• 迭代加深：limit = h(initial) 起始，逐層加深直到成功。

核心代碼 (C++)

#include 
using namespace std;

int N, limit;
int board[8][8];
int vis[8][8];
int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};

void dfsMark(int r, int c, int color) {
    if (r<0||r>=N||c<0||c>=N||vis[r][c]) return;
    if (board[r][c] == color) {
        vis[r][c] = 1;
        for (int d=0; d<4; ++d) dfsMark(r+dr[d], c+dc[d], color);
    } else vis[r][c] = 2;
}

int heuristic() {
    bool has[6] = {};
    for (int i=0;i limit) return false;

    int curColor = board[0][0];
    int backupBoard[8][8], backupVis[8][8];
    memcpy(backupBoard, board, sizeof(board));
    memcpy(backupVis, vis, sizeof(vis));

    for (int c = 0; c < 6; ++c) {
        if (c == curColor) continue;
        // 染色 c
        for (int i=0;i> N, N) {
        for (int i=0;i> board[i][j];
        memset(vis, 0, sizeof(vis));
        dfsMark(0, 0, board[0][0]);
        for (limit = heuristic(); ; ++limit)
            if (IDA(0)) break;
        cout << limit << '\n';
    }
    return 0;
}

優化點

• 顏色排序：優先嘗試邊界區域面積最大的顏色（統計 vis==2 各色計數），通常能更快找到解。
• 位掩碼狀態：用 64 位整數編碼棋盤，配合哈希表做遷移表去重（IDA* 通常不存 visited，但可加）。
• 對稱剪枝：避免連續兩步染同一顏色。

總結

HDU 4127 是 Flood-it 的標準 IDA* 解法。關鍵在於正確實現「連通區標記 → 染色 → 遞歸 → 回溯」流程，啟發函數取「邊界顏色種類數」簡單有效。N≤8 保證搜索深度極淺 (通常 ≤ 10)，迭代加深極快。