您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1253 勝利大逃亡：三維 BFS 迷宮最短路徑

編輯：關於C++

HDU 1253 勝利大逃亡詳解

題目：Ignatius 被關在 A×B×C 的立方體城堡中，起點 (0,0,0)，終點 (A-1,B-1,C-1)。每分鐘可移動到六個相鄰坐標（上下左右前後）。城堡地圖用 0/1 表示路/牆。魔王 T 分鐘後回來，求能否在 T 分鐘內逃出（到達出口瞬間魔王回來算成功），能則輸出最少分鐘數，否則 -1。多組測試數據，A,B,C ≤ 50，T ≤ 1000。

核心模型：三維無權圖最短路徑 → BFS

狀態：(z, x, y) 三維坐標。
轉移：六個方向 dz,dx,dy ∈ {(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)}。
目標：從起點到終點的最短步數（每步耗時 1 分鐘）。
約束：不越界、不撞牆 (map[z][x][y] != 1)、不重複訪問。

BFS 標準流程

隊列存儲 (z, x, y, time)。
起點入隊，標記訪問，time=0。
出隊檢查是否為終點，是則返回 time。
拓展六鄰居，合法且未訪問則入隊，time+1。
隊列空仍未到達終點 → 返回 -1。

關鍵優化與細節

輸入優化：題目數據量大，必須用 scanf / 快速 IO，C++ cin/cout 需關閉同步 ios::sync_with_stdio(false); cin.tie(nullptr);。
訪問標記：vis[z][x][y] 布爾陣列，入隊時標記，避免重複入隊導致 TLE/MLE。
方向數組：int dir[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; 對應 z,x,y 三維。
多測試用例：每輪 memset 清空 vis 與 map。
時間限制判斷：BFS 找到最短步數 ans 後，若 ans <= T 輸出 ans，否則 -1。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

struct Node { int z, x, y, t; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int K; cin >> K;
    while (K--) {
        int A, B, C, T; cin >> A >> B >> C >> T;
        vector> maze(A, vector(B));
        for (int z = 0; z < A; ++z)
            for (int x = 0; x < B; ++x)
                cin >> maze[z][x];

        vector>> vis(A, vector>(B, vector(C, false)));
        queue q;
        q.push({0, 0, 0, 0});
        vis[0][0][0] = true;
        int ans = -1;
        int dz[6] = {1,-1,0,0,0,0};
        int dx[6] = {0,0,1,-1,0,0};
        int dy[6] = {0,0,0,0,1,-1};

        while (!q.empty()) {
            Node cur = q.front(); q.pop();
            if (cur.z == A-1 && cur.x == B-1 && cur.y == C-1) {
                ans = cur.t; break;
            }
            for (int i = 0; i < 6; ++i) {
                int nz = cur.z + dz[i], nx = cur.x + dx[i], ny = cur.y + dy[i];
                if (nz < 0 || nz >= A || nx < 0 || nx >= B || ny < 0 || ny >= C) continue;
                if (vis[nz][nx][ny] || maze[nz][nx][ny] == '1') continue;
                vis[nz][nx][ny] = true;
                q.push({nz, nx, ny, cur.t + 1});
            }
        }
        if (ans != -1 && ans <= T) cout << ans << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}