HDU 1072 Nightmare：帶炸彈倒計時的迷宮 BFS

問題描述

n,m ≤ 8 的迷宮，格子類型：0 牆、1 空地、2 起點、3 終點、4 炸彈重置裝置（將倒計時重置為 6）。初始倒計時 6，每移動一步（上下左右）消耗 1 時間。倒計時歸零前必須到達終點；若在倒計時歸零時刻踏上重置裝置，無法重置（視為失敗）。可重複經過格子、重複使用重置裝置。求最少步數，不可達輸出 -1。

狀態空間與 BFS

狀態 = (x, y, time_left)。time_left ∈ [1,6]（0 即死亡）。總狀態數 ≤ 8*8*6 = 384，極小。BFS 保證最短步數。

轉移：從 (x,y,t) 向四方向嘗試移動到 (nx,ny)：

• 若越界或為牆，跳過。
• 新時間 nt = t - 1。若 nt == 0，該移動非法（無論目標格子類型）。
• 若目標為重置裝置 (4)，nt = 6。
• 若目標為終點 (3)，返回步數+1。
• 若狀態 (nx,ny,nt) 未訪問，入隊。

訪問標記

用 vis[x][y][time] 或將時間編入狀態編碼。注意：同一格子不同時間剩餘視為不同狀態，因為剩餘時間影響後續可行性。

參考代碼 (C++)

#include 
using namespace std;
struct Node { int x, y, t, step; };
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
int maze[10][10], vis[10][10][7];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        Node start;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                scanf("%d", &maze[i][j]);
                if (maze[i][j] == 2) start = {i, j, 6, 0};
            }
        memset(vis, 0, sizeof(vis));
        queue q;
        q.push(start);
        vis[start.x][start.y][start.t] = 1;
        int ans = -1;
        while (!q.empty()) {
            Node cur = q.front(); q.pop();
            for (int d = 0; d < 4; ++d) {
                int nx = cur.x + dx[d], ny = cur.y + dy[d];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (maze[nx][ny] == 0) continue;
                int nt = cur.t - 1;
                if (nt == 0) continue; // 時間耗盡，不可移動
                if (maze[nx][ny] == 4) nt = 6; // 重置
                if (maze[nx][ny] == 3) { ans = cur.step + 1; goto END; }
                if (!vis[nx][ny][nt]) {
                    vis[nx][ny][nt] = 1;
                    q.push({nx, ny, nt, cur.step + 1});
                }
            }
        }
        END:
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點總結

• 狀態包含剩餘時間，將時間資源離散化為 BFS 層級一部分。
• 時間歸零前必須完成移動，且重置發生在移動後（新格子生效）。
• goto 簡化跳出雙重循環，或用標誌變量。
• 數據範圍極小，BFS 瞬間結束。