HDU 1242 營救天使：BFS 最短路徑含守衛代價的完整解析

問題描述

在 N×M 矩陣（N,M ≤ 200）迷宮中，包含牆壁(#)、道路(.)、天使(a)、朋友(r)、守衛(x)。移動上下左右耗時 1，殺死守衛額外耗時 1。求朋友到達天使的最短時間，不可達輸出 Poor ANGEL has to stay in the prison all his life.

算法選型：狀態擴展的 BFS

標準 BFS 假設邊權為 1，但「遇守衛 +1」導致邊權為 1 或 2。解決方案：

• 將「殺守衛」視為在該格多停留 1 秒
• 隊列節點攜帶 time 字段，而非層次遍歷
• 剪枝：next.time < step[next.x][next.y] 才入隊（step 記錄到達該格最短時間）

核心代碼實現

#include <cstdio>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
const int maxn = 200 + 10;
using namespace std;

int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
int step[maxn][maxn];
int n, m, sum;
char map[maxn][maxn];

struct Map { int x, y, time; };
queue<Map> q;
Map start, end;

int check(int x, int y) {
    return x>=1 && x<=n && y>=1 && y<=m;
}

int bfs() {
    Map current, next;
    memset(step, 0x3f, sizeof(step));
    step[start.x][start.y] = 0;
    q.push(start);
    int ans = INF;

    while (!q.empty()) {
        current = q.front(); q.pop();
        if (current.time >= ans) continue;  // 剪枝

        for (int i = 0; i < 4; i++) {
            next.x = current.x + dx[i];
            next.y = current.y + dy[i];
            next.time = current.time + 1;

            if (map[next.x][next.y] == 'x') next.time++;  // 遇守衛+1

            if (check(next.x, next.y) && map[next.x][next.y] != '#' 
                && next.time < step[next.x][next.y]) {
                step[next.x][next.y] = next.time;
                if (next.x == end.x && next.y == end.y) {
                    ans = min(ans, next.time);
                } else {
                    q.push(next);
                }
            }
        }
    }
    return ans == INF ? -1 : ans;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++) {
            scanf("%s", map[i] + 1);
            for (int j = 1; j <= m; j++) {
                if (map[i][j] == 'a') end.x = i, end.y = j;
                if (map[i][j] == 'r') start.x = i, start.y = j, start.time = 0;
            }
        }
        int ans = bfs();
        if (ans == -1)
            puts("Poor ANGEL has to stay in the prison all his life.");
        else
            printf("%d\n", ans);
    }
    return 0;
}

關鍵點深度解析

1. 時間狀態而非層次

傳統 BFS 用隊列大小控制層次，本題因邊權不一，改用節點攜帶 time，step[][] 記錄最短到達時間，實現類 Dijkstra 的 BFS 變體（因邊權僅 1/2，不需優先隊列）。

2. 剪枝優化

if (current.time >= ans) continue;  // 已找到更優解
if (next.time < step[next.x][next.y]) { ... }  // 只有更優才入隊

作者提到「0ms 通過」，得益於此剪枝。

3. 多測試用例處理

while (scanf("%d%d", &n, &m) == 2) 讀到 EOF 結束，每輪重置全局狀態。

4. 坐標系統

採用 1-based 索引，check() 邊界判斷簡潔：x>=1 && x<=n && y>=1 && y<=m。

樣例測試

Input:
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Output:
13

複雜度分析

• 時間：O(N×M) 每個格子最多入隊常數次
• 空間：O(N×M) 隊列 + step 數組 + 地圖

常見坑點

1. 守衛格子 x 可通行但 +1 時間，非障礙物
2. 多個朋友(r)？題目隱含單起點，代碼覆蓋 start 取最後一個
3. 輸入行可能含空格？用 %s 讀取跳過空白
4. 輸出格式嚴格：大小寫、標點需完全匹配

總結

HDU 1242 是經典的「帶權障礙 BFS」入門題，核心在於將非均勻邊權轉化為節點時間狀態，配合 step[][] 剪枝實現高效求解。代碼簡潔、邏輯清晰，是 BFS 進階的優秀教學案例。