HDU 1253 勝利大逃亡：三維 BFS + 剪枝優化完整解析

題目大意

在 A×B×C 的三維網格中（A,B,C ≤ 50），從 (0,0,0) 走到 (A-1,B-1,C-1)。格子為 0（可通行）或 1（阻礙）。六個方向移動（上下左右前後），每步耗時 1。給定時間限制 T，求最短到達時間；若超過 T 或無路徑，輸出 -1。多組測資。

核心算法：三維 BFS

BFS 保證找到最短路（無權圖）。狀態：(x,y,z,dist)。訪問標記 vis[x][y][z] 防重複入隊。

關鍵剪枝：曼哈頓距離下界

當前狀態 (x,y,z) 到終點的最短可能步數 = (A-1-x) + (B-1-y) + (C-1-z)。若 dist + lowerBound > T，該狀態不可能在時限內到達，直接捨棄不入隊。此剪枝極大減少狀態空間。

完整 AC 代碼

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <map>
using namespace std;

#define Lowbit(x) ((x)&(-(x)))
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define mod 10000007
#define MAXN 100010
#define INF 1e9
#define Max 100010

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

bool vis[55][55][55];
int grid[55][55][55];
int dx[6] = {0,0,0,0,1,-1};
int dy[6] = {0,1,0,-1,0,0};
int dz[6] = {1,0,-1,0,0,0};
int A, B, C, T;

bool check(int x, int y, int z) {
    return x >= 0 && x < A && y >= 0 && y < B && z >= 0 && z < C
        && !vis[x][y][z] && !grid[x][y][z];
}

int main() {
    int K;
    scanf("%d", &K);
    while (K--) {
        queue<Node> q;
        scanf("%d%d%d%d", &A, &B, &C, &T);
        memset(vis, false, sizeof(vis));
        memset(grid, 0, sizeof(grid));
        for (int i = 0; i < A; ++i)
            for (int j = 0; j < B; ++j)
                for (int k = 0; k < C; ++k)
                    scanf("%d", &grid[i][j][k]);

        int ans = -1;
        if (!grid[0][0][0] && !grid[A-1][B-1][C-1]) {
            q.push({0,0,0,0});
            vis[0][0][0] = true;
            while (!q.empty()) {
                Node now = q.front(); q.pop();
                if (now.cost > T) break;
                if (now.x == A-1 && now.y == B-1 && now.z == C-1) {
                    ans = now.cost;
                    break;
                }
                for (int i = 0; i < 6; ++i) {
                    Node nxt = {now.x + dx[i], now.y + dy[i], now.z + dz[i], now.cost + 1};
                    if (check(nxt.x, nxt.y, nxt.z)) {
                        // 曼哈頓距離剪枝
                        int lb = abs(nxt.x - (A-1)) + abs(nxt.y - (B-1)) + abs(nxt.z - (C-1));
                        if (nxt.cost + lb > T) continue;
                        vis[nxt.x][nxt.y][nxt.z] = true;
                        q.push(nxt);
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 狀態數上限：A×B×C ≤ 125,000
• 時間：O(ABC) 最壞，剪枝後實際極快
• 空間：O(ABC) 訪問陣列 + 隊列

關鍵細節總結

1. 六方向移動：dx/dy/dz 覆蓋 ±x, ±y, ±z
2. 起點/終點阻礙檢查：若起點或終點為 1，直接輸出 -1
3. 訪問標記入隊時打標：避免重複入隊導致指數爆炸
4. 曼哈頓剪枝：dist + |dx|+|dy|+|dz| > T 則捨棄，核心優化
5. 時間限制檢查：出隊時 if (now.cost > T) break;，因 BFS 按層擴展，後續層必更大
6. 多測資清理：每組 memset 重置陣列

測試建議

1
3 3 3 10
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
# 最短路徑長度 = (3-1)*3 = 6
輸出：6

總結

三維 BFS + 曼哈頓距離剪枝是網格最短路限時問題的標準解法。關鍵在於狀態定義、訪問標記時機、可行性下界剪枝三點。此模板可直接遷移至二維/四維、帶狀態（鑰匙/門）、多起點/終點等變體。