POJ 1324 Holedox Moving：A* 優化 BFS 求貪食蛇最短路徑

問題描述

迷宮中有一條長度 L (≤ 9) 的貪食蛇，頭在 (x₀,y₀)，身體佔據連續格子。蛇每次移動：頭向四向之一前進一格，尾巴縮回（保持長度）。牆壁不可通過。求蛇頭到達左上角 (1,1) 的最少步數。N,M ≤ 20。

狀態編碼：壓縮蛇身相對方向

蛇身固定長度 L，頭位置 (x,y) + L-1 個方向（上/下/左/右，2 位編碼）唯一確定全身位置。
狀態 = (x, y, code)，code 為 2(L-1) 位整數（L≤9 → code < 2¹⁶ = 65536）。
總狀態數 ≤ 20×20×65536 ≈ 2.6×10⁷，需優化搜索。

A* 算法：啟發式函數 h = 曼哈頓距離

從當前頭位置 (x,y) 到目標 (1,1) 的曼哈頓距離 |x-1| + |y-1| 是可接受啟發式（不超過實際最短步數）。
優先隊列按 f = g + h 排序（g 為已走步數）。
A* 發現重複狀態時直接捨棄（不更新），因啟發式單調，首次到達必為最短路。

關鍵操作

• 編碼：從頭到尾，記錄相鄰段方向（0:右, 1:左, 2:下, 3:上）。
• 解碼：從頭位置按方向碼重建全身坐標（用於碰撞檢測）。
• 移動：新頭坐標 + 新方向碼 = (舊碼 << 2 | 反方向) & mask。
• 合法性檢查：新頭不出界、非牆壁、非蛇身（解碼後遍歷身體坐標）。

代碼框架

struct State { int x, y, code, g, f; };
bool operator<(State a, State b) { return a.f > b.f; } // 小頂堆
int encode(State s) { /* ... */ }
State move(State s, int dir) { /* ... */ }
bool valid(State s) { /* 解碼檢查牆壁、身體碰撞 */ }
int astar() {
    priority_queue pq;
    pq.push({sx, sy, initCode, 0, sx+sy});
    vis[sx][sy][initCode] = 1;
    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        if (cur.x==1 && cur.y==1) return cur.g;
        for (int d=0; d<4; d++) {
            State nxt = move(cur, d);
            nxt.g = cur.g + 1;
            nxt.f = nxt.g + abs(nxt.x-1) + abs(nxt.y-1);
            if (valid(nxt) && !vis[nxt.x][nxt.y][nxt.code]) {
                vis[nxt.x][nxt.y][nxt.code] = 1;
                pq.push(nxt);
            }
        }
    }
    return -1;
}

複雜度

• 狀態空間大，但 A* 大幅剪枝，實際訪問狀態遠少於 BFS。
• 訪問標記用 vis[21][21][1<<16]（約 27M bool），內存 ~27MB，可接受。
• 運行時間通常 < 1s。

總結

POJ 1324 是狀態壓縮 + A* 搜索的經典硬題。關鍵在於：
1. 蛇身相對方向編碼（極其緊湊）
2. 曼哈頓距離作為可接受啟發式
3. A* 首次到達即最優，無需更新重複狀態
掌握此模板，可解決大類「固定長度移動實體（蛇、火車、機器人）」的最短路問題。