UVA 11624 Fire!：雙 BFS 解決火災逃生最短路徑

問題建模

R×C 迷宮（R,C ≤ 1000），Joe 起始位置 J，多個火源 F，牆壁 #。Joe 每分鐘移動上下左右一格，火同時向四方向蔓延。Joe 到達邊界格即視為逃脫。求最短逃脫時間，或輸出 IMPOSSIBLE。

雙 BFS 核心策略

關鍵洞察：火的蔓延與 Joe 的移動同步進行。可預先計算每個格子著火時間 fire_time[r][c]，然後 Joe 的 BFS 中只允許移動到 joe_time + 1 < fire_time[nr][nc] 的格子（嚴格小於，同一分鐘到達也會被燒）。

算法步驟

1. 多源 BFS 計算火勢時間：將所有初始火源入隊，fire_time = 0。標準 BFS 擴展，記錄每格最早著火分鐘數。未到達格設為 INF。
2. 單源 BFS 模擬 Joe 逃脫：從 J 開始，joe_time = 0。擴展時檢查：

• 目標格非牆壁。
• joe_time + 1 < fire_time[nr][nc]（下一分鐘到達前該格未著火）。
• 若目標格在邊界（r=0 或 R-1 或 c=0 或 C-1），直接返回 joe_time + 1（步數+1 因起始算第 0 分鐘）。

代碼關鍵片段

const int INF = 0x3f3f3f3f;
int dr[4] = {-1,0,1,0}, dc[4] = {0,1,0,-1};

void bfs_fire() {
    queue> q;
    // 初始化火源
    for (int i=0;i=R||nc<0||nc>=C||grid[nr][nc]=='#') continue;
            if (fire_time[nr][nc] > fire_time[r][c] + 1) {
                fire_time[nr][nc] = fire_time[r][c] + 1;
                q.emplace(nr,nc);
            }
        }
    }
}

int bfs_joe() {
    queue> q; // r, c, time
    q.emplace(sr, sc, 0);
    joe_vis[sr][sc] = true;
    while (!q.empty()) {
        auto [r,c,t] = q.front(); q.pop();
        if (r==0 || r==R-1 || c==0 || c==C-1) return t + 1; // 逃脫
        for (int d=0;d<4;++d) {
            int nr=r+dr[d], nc=c+dc[d];
            if (nr<0||nr>=R||nc<0||nc>=C||grid[nr][nc]=='#'||joe_vis[nr][nc]) continue;
            if (t + 1 >= fire_time[nr][nc]) continue; // 關鍵條件
            joe_vis[nr][nc] = true;
            q.emplace(nr, nc, t+1);
        }
    }
    return -1; // IMPOSSIBLE
}

複雜度與細節

• 時間 O(RC)，空間 O(RC)，R,C ≤ 1000 時約 10⁶ 格，雙 BFS 極快。
• 火源可能為 0，需處理（fire_time 全 INF）。
• Joe 起始位置可能在邊界，直接返回 1。
• 輸入多測試用例，需清空隊列與數組。

總結

UVA 11624 是「多源 BFS 預處理環境變化 + 單源 BFS 決策」的經典模式。將動態障礙（火）轉化為靜態時間場 fire_time，將時空耦合問題解耦為兩個獨立 BFS，是處理「移動實體與擴散障礙」類問題的通用技巧。