HDU 2102 A計劃：雙層迷宮 BFS 最短路 (傳送門機制)

問題描述

兩層 N×M 迷宮 (N,M≤10)，入口 S(0,0,0)，公主 P，牆 *、路 .、傳送門 #。移動：同層上下左右耗時 1；踩傳送門瞬間傳送至另一層同座標（若目標是牆則死）。T 時刻前救到公主輸出 YES，否則 NO。

BFS 狀態設計

• 狀態：(層z, 行x, 列y, 時間t)
• 起點固定 (0,0,0)，非輸入中 'S' 位置（易錯點）
• 訪問標記 vis[2][N][M]
• 傳送門處理：踩到 # 時嘗試切換層，目標非牆則入隊，時間不增加

核心 BFS 邏輯

int bfs() {
    queue q; memset(vis,0,sizeof(vis));
    q.push({0,0,0,0}); vis[0][0][0]=1;
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        if (cur.z==ez && cur.x==ex && cur.y==ey) return cur.t<=T;
        for (int d=0; d<4; d++) {
            int nx=cur.x+dx[d], ny=cur.y+dy[d], nz=cur.z;
            if (out of bounds || vis[nz][nx][ny] || g[nz][nx][ny]=='*') continue;
            vis[nz][nx][ny]=1;
            if (g[nz][nx][ny]!='#') q.push({nz,nx,ny,cur.t+1});
            else { // 傳送門
                int tz = 1-nz;
                if (!vis[tz][nx][ny] && g[tz][nx][ny]!='*') {
                    if (g[tz][nx][ny]!='#') q.push({tz,nx,ny,cur.t+1});
                    // 目標也是 # 則不再傳送（避免無限循環），但題目保證不會雙層都是 # 且非牆
                }
            }
        }
    }
    return 0;
}

關鍵坑點總結

1. 起點強制 (0,0,0)，忽略地圖中 'S' 位置
2. 時間 ≤ T 即可，非嚴格 <
3. 雙層均為 # 時，傳送目標若為牆則死，否則正常傳送（代碼中雙層 # 視為不傳送或傳送一次）
4. 訪問標記在入隊時設置，防止重複入隊

樣例

輸入:
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
輸出: YES