HDU 2102 A計劃：BFS 配合優先隊列求解最短路徑詳解

這道題目屬於經典的 BFS 配合優先隊列應用。初見四分之一的 AC 率略感壓力，實際著手後發現只需在標準 BFS 模板上稍作修改即可一次通過。不過在主函數與全域變數中重複定義 n、m 卻讓我白白浪費了不少除錯時間，再次驗證了全域變數使用需謹慎的教訓。

核心資料結構設計

與普通 BFS 模板類似，定義結構體節點，額外增加一個「迷宮層數」參數：用 0 代表第一層，1 代表第二層，這在陣列索引中會直觀體現。

struct Node {
    int index; // 層數：0 或 1
    int x, y;  // 座標
    int time;  // 到達此點所需時間
    // 優先隊列比較函數：時間少的優先
    friend bool operator<(const Node &a, const Node &b) {
        return a.time > b.time;
    }
};

迷宮地圖與可行性檢測

地圖採用三維陣列 char map[2][11][11]，第一維為層數。can_go 函數負責檢測指定層、座標是否可通行（未越界且非牆壁 '*'）。

傳送門機制處理

本題關鍵差異在於傳送門 '#' 的處理：遇到傳送門時，先將當前層該格標記為已訪問，隨即嘗試瞬間移動到另一層同座標。若另一層該處是牆壁 '*' 或同樣是傳送門 '#'，則說明此路不通，直接 continue 嘗試其他方向。

if (map[!next.index][next.x][next.y] == '*' || 
    map[!next.index][next.x][next.y] == '#') {
    continue;
}

BFS 主流程

優先隊列非空時循環：取出隊首節點，若時間超限 T 則返回 -1；若到達終點 'P' 返回當前時間。否則向四個方向擴展，合法且未訪問的格子入隊，時間 +1。若新格為傳送門且另一層同位置合法，則切換層數並同步標記訪問、入隊。

完整參考代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

char map[2][11][11];
int vis[2][11][11];
int t, n, m;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

struct Node {
    int index, x, y, time;
    friend bool operator<(const Node &a, const Node &b) {
        return a.time > b.time;
    }
};

int can_go(int index, int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || map[index][x][y] == '*')
        return 0;
    return 1;
}

int bfs(int index, int x, int y) {
    priority_queue<Node> que;
    Node now, next;
    memset(vis, 0, sizeof(vis));
    now = {index, x, y, 0};
    vis[index][x][y] = 1;
    que.push(now);

    while (!que.empty()) {
        now = que.top(); que.pop();
        if (now.time > t) return -1;
        if (map[now.index][now.x][now.y] == 'P') return now.time;

        for (int i = 0; i < 4; ++i) {
            next.index = now.index;
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];
            if (!vis[next.index][next.x][next.y] && can_go(next.index, next.x, next.y)) {
                vis[next.index][next.x][next.y] = 1;
                if (map[next.index][next.x][next.y] == '#' && !vis[!next.index][next.x][next.y]) {
                    if (map[!next.index][next.x][next.y] == '*' || 
                        map[!next.index][next.x][next.y] == '#') continue;
                    next.index = !next.index;
                    vis[next.index][next.x][next.y] = 1;
                }
                next.time = now.time + 1;
                que.push(next);
            }
        }
    }
    return -1;
}

int main() {
    int c; scanf("%d", &c);
    while (c--) {
        scanf("%d%d%d", &n, &m, &t);
        for (int i = 0; i < n; ++i) scanf("%s", map[0][i]);
        for (int i = 0; i < n; ++i) scanf("%s", map[1][i]);
        int sx, sy;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (map[0][i][j] == 'S') { sx = i; sy = j; }
        printf("%d\n", bfs(0, sx, sy));
    }
    return 0;
}