HDOJ 1242 Rescue：BFS 迷宮最短時間（守衛殺敵耗時）

題目大意

N×M (≤ 200) 迷宮：'.' 路、'#' 牆、'a' 天使(終點)、'r' 朋友(起點，可能多個)、'x' 守衛。移動上下左右 1 時間，殺守衛額外 1 時間（進入 'x' 格共 2 時間）。多起點求到終點最短時間。不可達輸出提示語。

解法：多源 Dijkstra / 0-1 BFS / 優先隊列 BFS

邊權為 1 (普通路) 或 2 (守衛)。可用優先隊列 (Dijkstra) 或雙端隊列 (0-1 BFS 變體，權 1/2 不直接適用)。本題用優先隊列最簡單。

關鍵代碼

#include 
#include 
#include 
using namespace std;
const int MAX = 205;
char maze[MAX][MAX];
int dist[MAX][MAX];
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

struct Node {
    int x, y, d;
    bool operator<(const Node& o) const { return d > o.d; } // 小頂堆
};

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 0; i < n; ++i) scanf("%s", maze[i]);
        memset(dist, 0x3f, sizeof(dist));
        priority_queue pq;
        int ex, ey;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (maze[i][j] == 'r') {
                    dist[i][j] = 0;
                    pq.push({i, j, 0});
                }
                if (maze[i][j] == 'a') { ex = i; ey = j; }
            }
        while (!pq.empty()) {
            Node cur = pq.top(); pq.pop();
            if (cur.d != dist[cur.x][cur.y]) continue;
            if (cur.x == ex && cur.y == ey) break;
            for (int dir = 0; dir < 4; ++dir) {
                int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
                if (nx<0||nx>=n||ny<0||ny>=m||maze[nx][ny]=='#') continue;
                int nd = cur.d + (maze[nx][ny] == 'x' ? 2 : 1);
                if (nd < dist[nx][ny]) {
                    dist[nx][ny] = nd;
                    pq.push({nx, ny, nd});
                }
            }
        }
        if (dist[ex][ey] == 0x3f3f3f3f)
            puts("Poor ANGEL has to stay in the prison all his life.");
        else
            printf("%d\n", dist[ex][ey]);
    }
    return 0;
}

複雜度

• 節點 ≤ 40000，邊 ≤ 160000。Dijkstra O(E log V) 極快。

關鍵點

• **多源**：所有 'r' 入隊距離 0。
• **邊權 1/2**：優先隊列自動處理。
• **終止條件**：彈出終點時即為最短距離。
• **不可達判斷**：dist 保持 INF。

總結

HDOJ 1242 是帶權迷宮最短路的標準題。多源 Dijkstra 完美解決，代碼簡潔。注意 'x' 格代價為 2，其餘為 1。輸出格式需完全匹配樣例。