HDU 1072 Nightmare：炸彈倒數下的迷宮逃脫

這是一道經典的廣度優先搜索（BFS）題目，編號 HDU 1072，名為 Nightmare。題目描述 Ignatius 在惡夢中被困在一個迷宮裡，身上綁著定時炸彈，初始倒數 6 分鐘。他必須在炸彈爆炸前找到出口。迷宮中分佈著「炸彈重置裝置」，踩上去可將倒數時間重置為 6 分鐘。移動規則為每分鐘只能向上下左右四個相鄰格子移動一步，不能撞牆、不能出界。關鍵限制：若在倒數歸零的瞬間到達出口或重置裝置，均視為失效。

問題建模與狀態設計

這是一個帶狀態的最短路徑問題。狀態需包含：座標 (x, y)、剩餘時間 time。由於時間只有 1~6 分鐘，且格子大小 ≤ 8×8，狀態總數極小（8×8×6 = 384），非常適合 BFS。

為了避免重複搜索，需記錄每個格子在「剩餘時間 ≥ 某值」時是否已被訪問。定義 vis[x][y][t] 表示在位置 (x,y) 且剩餘時間 至少為 t 的狀態已入隊。若新到達狀態的剩餘時間 ≤ 已記錄的最大剩餘時間，則無需再次入隊（因為剩餘時間越多越有優勢）。

核心邏輯

• 起點：值為 2 的格子，初始時間 6。
• 終點：值為 3 的格子，到達時剩餘時間必須 > 0。
• 重置裝置：值為 4 的格子，進入時若剩餘時間 > 0，時間重置為 6。
• 牆壁：值為 0，不可通行。
• 空地：值為 1，可通行。

BFS 隊列存儲 (x, y, time, steps)。每次拓展四個方向，新時間 nt = time - 1。若 nt == 0 則該路徑失效。若新格子為重置裝置且 nt > 0，則 nt = 6。若新格子為出口且 nt > 0，返回當前步數+1。利用 vis[x][y][nt] 剪枝。

參考代碼 (C++)

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

struct Node {
    int x, y, time, step;
};

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int maze[10][10];
int vis[10][10][7]; // vis[x][y][t] 表示剩餘時間 >= t 已訪問

int main() {
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        Node start;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> maze[i][j];
                if (maze[i][j] == 2) start = {i, j, 6, 0};
            }

        queue<Node> q;
        q.push(start);
        vis[start.x][start.y][6] = 1;
        int ans = -1;

        while (!q.empty()) {
            Node cur = q.front(); q.pop();
            if (maze[cur.x][cur.y] == 3) { ans = cur.step; break; }
            for (auto &d : dir) {
                int nx = cur.x + d[0], ny = cur.y + d[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (maze[nx][ny] == 0) continue; // 牆
                int nt = cur.time - 1;
                if (nt == 0) continue; // 時間耗盡
                if (maze[nx][ny] == 4) nt = 6; // 重置裝置
                // 剪枝：若已有剩餘時間 >= nt 的記錄，跳過
                bool skip = false;
                for (int t = nt; t <= 6; ++t)
                    if (vis[nx][ny][t]) { skip = true; break; }
                if (skip) continue;
                vis[nx][ny][nt] = 1;
                q.push({nx, ny, nt, cur.step + 1});
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

關鍵點總結

1. 狀態包含時間維度，將問題轉化為三維 BFS。
2. 訪問標記優化：只記錄「剩餘時間 ≥ t」的最優狀態，避免冗餘搜索。
3. 邊界條件嚴格：時間歸零瞬間不可觸發出口或重置裝置。
4. 數據範圍小，無需複雜優化，標準 BFS 即可輕鬆通過。

這道題是練習「帶狀態 BFS」的優秀入門題，掌握其狀態設計與剪枝技巧，對解決類似「限時、可重置、多狀態」的圖論問題大有裨益。