您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

HDU 1072 Nightmare：BFS 解迷宮與炸彈倒數問題詳解

編輯：Java 綜合教學

HDU 1072 Nightmare：BFS 解迷宮與炸彈倒數問題詳解

這是一道經典的廣度優先搜索（BFS）題目，背景設定為：Ignatius 身陷迷宮，身上綁著定時炸彈，初始倒數 6 分鐘。他必須在炸彈爆炸前找到出口。迷宮以二維數組表示，每移動一步（上下左右）耗時 1 分鐘。部分格子設有「炸彈重置裝置」，踏上後可將倒數重置為 6 分鐘。目標是判斷能否逃出，若能則輸出最短時間，否則輸出 -1。

題目規則重點

迷宮大小 N、M ≤ 8。
地圖元素：0=牆壁，1=空地，2=起點，3=終點，4=重置裝置。
若到達終點或重置裝置時倒數剛好歸零，則視為失敗（無法使用裝置、無法逃出）。
重置裝置可重複使用，路徑可重複走。
重置動作不消耗時間，即踏上格子的瞬間若倒數 > 0，立即重置為 6。

解題思路：狀態擴展的 BFS

普通 BFS 只記錄座標與步數，但本題引入「剩餘時間」作為狀態維度。同一格子在不同時間到達，後續可行路徑不同。因此狀態定義為 (x, y, timeLeft, steps)。

訪問標記採用 vis[x][y] 記錄該格子曾經擁有的「最大剩餘時間」。若新到達時的剩餘時間 ≤ 已記錄值，則該狀態無優勢，直接剪枝。這利用了「時間越多越有利」的單調性。

關鍵邏輯

起始狀態：(xs, ys, 6, 0)。若起點即終點且時間 > 0，直接輸出 0。
出隊擴展四個方向，邊界檢查、牆壁檢查。
新剩餘時間 = 當前時間 - 1。若新時間 ≤ 0，該移動無效（規則 3、4）。
若目標格為 4，重置時間為 6。
若 newTime > vis[tx][ty]，更新 vis 並入隊。
若到達終點且時間 > 0，輸出步數並結束。
隊列耗盡仍未到達終點，輸出 -1。

參考代碼（C++）

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

struct Node {
    int x, y, t, step;
    Node(int a=0,int b=0,int c=0,int d=0):x(a),y(b),t(c),step(d){}
    void set(int a,int b,int c,int d){x=a;y=b;t=c;step=d;}
};

int n, m, xs, ys, xe, ye;
int mat[10][10];
int vis[10][10];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

void bfs() {
    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    Node start(xs, ys, 6, 0);
    if (start.x == xe && start.y == ye && start.t > 0) {
        printf("%d\n", start.step);
        return;
    }
    q.push(start);
    vis[xs][ys] = 6;

    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int tx = cur.x + dir[i][0];
            int ty = cur.y + dir[i][1];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
            if (mat[tx][ty] == 0) continue;

            int nt = cur.t - 1;
            if (nt <= 0) continue; // 時間耗盡，不可移動

            if (mat[tx][ty] == 4) nt = 6; // 重置裝置

            if (nt <= vis[tx][ty]) continue; // 無優勢
            vis[tx][ty] = nt;

            Node nxt(tx, ty, nt, cur.step + 1);
            if (tx == xe && ty == ye) {
                printf("%d\n", nxt.step);
                return;
            }
            q.push(nxt);
        }
    }
    printf("-1\n");
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                scanf("%d", &mat[i][j]);
                if (mat[i][j] == 2) { xs = i; ys = j; }
                if (mat[i][j] == 3) { xe = i; ye = j; }
            }
        }
        bfs();
    }
    return 0;
}