HDU 5025 Saving Tang Monk：BFS + 狀態壓縮（鑰匙順序 + 蛇位圖）

問題描述

N×N 迷宮，包含：起點 K、終點 T、牆 #、空地 .、蛇 S（最多 5 條）、數字鑰匙 1~9（順序獲取）。經過蛇格子第一次需額外花費 1 時間（咬傷），後續免疫。鑰匙必須按 1,2,3... 順序撿起。求從 K 到 T 且收集齊所有鑰匙的最短時間，不可達輸出 "impossible"。多測試用例。

狀態壓縮 BFS

• 狀態：(x, y, keys, snakes, time)
  • keys：已獲取的最大鑰匙編號（0~9），因順序固定，單整數即可。
  • snakes：蛇咬傷狀態位圖（最多 5 條蛇 → 5 位，1<<5 = 32 種）。
• 狀態數：N≤100，100×100×10×32 = 3.2×10^6，可用優先隊列（Dijkstra，因邊權 1 或 2）或 0-1 BFS（雙端隊列）。
• 優先隊列按 time + popcount(snakes) 排序（A* 啟發式），或直接用普通 BFS（因邊權均為 1，蛇咬傷視為進入該格額外 +1 步，可拆分為兩步或狀態帶時間）。

代碼框架（優先隊列版）

struct State {
    int x, y, keys, snakes, time;
    bool operator<(const State& o) const {
        return time + __builtin_popcount(snakes) > o.time + __builtin_popcount(o.snakes);
    }
};

int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
int snake_id[105][105];  // -1 非蛇，0~4 蛇編號

int bfs() {
    memset(vis, 0, sizeof(vis));
    priority_queue pq;
    pq.push({sx, sy, 0, 0, 0});
    vis[sx][sy][0][0] = 1;
    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        if (cur.keys == M && cur.x == tx && cur.y == ty)
            return cur.time + __builtin_popcount(cur.snakes);
        for (int d=0; d<4; ++d) {
            int nx=cur.x+dx[d], ny=cur.y+dy[d];
            if (out of bound or wall) continue;
            State nxt = cur;
            nxt.time++;
            char c = grid[nx][ny];
            if (c == 'S') {
                int id = snake_id[nx][ny];
                if (!(cur.snakes & (1<

複雜度
狀態數 ≤ 320 萬，優先隊列 log 因子，單測試用例 < 1s。

關鍵點

鑰匙順序固定 → 單整數記錄最大編號。
蛇免疫一次 → 位圖記錄已咬傷蛇。
時間計算：移動 1 步，初次經過蛇額外 +1（用 popcount(snakes) 累加）。
優先隊列啟發式 time + popcount 加速（A*）。