UVA-11624 Fire! 解題紀錄

🔗 UVA-11624 Fire!

tags: CPE-20230321 CPE-20161004 BFS 佇列(Queue)

C++ 範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上測試通過。
Python 範例程式碼僅能通過 瘋狂程設(CPE)、ZeroJudge 上的測試。

題意

Joe 在一個著火的迷宮裡，給定一個迷宮的地圖，其中 # 代表牆壁、. 代表可通行的區域、J 代表 Joe 的初始位置、F 代表著火的區域。Joe 每分鐘可以向上下左右移動一格(不能斜著走)，而火勢會從著火的區域向上下左右四周蔓延。Joe 必須在火勢追上他之前，從迷宮的邊緣逃脫出去。

輸出逃出迷宮的最短時間，如果 Joe 無法在火到達之前逃出迷宮，則輸出 IMPOSSIBLE。

思路：BFS 搶地盤

首先確定思路，對於 Joe 可到達的格子，顯然火焰之後能不能燃燒到這個格子是不重要的，因為 Joe 只要能在火到達之前逃出迷宮即可，故火焰事實上 不需要 擴散到 Jack 已經到達的格子上。因此我們可以使用類似 搶占地盤 的策略，將 Jack 和 火焰可以搶佔到的格子打上標記，最後檢查邊緣處是否有 Jack 的標記即可。

為此可以使用 BFS 來解決這個問題，Joe 和火焰共用一個佇列，每次從佇列中取出一個節點，如果是 Joe，則擴展他的可到達範圍，如果是火焰，則擴展火焰的蔓延範圍。而根據範例二，在同一時間時是火焰先擴散，所以我們可以先將火焰的位置加入佇列，再加入 Joe 的位置，這樣可以確保 Joe 和火焰都能按照順序更新位置。

為了節省對已標記位置的判斷，並且不直接修改迷宮的地圖，這裡只使用一個二維boolean陣列 $vis$ 來標記已經訪問過的格子，並將無法到達的格子（即牆壁）標記為已訪問，這樣可以確保每個格子只被訪問一次，且只需要判斷 $vis$ 陣列即可。但由於我們還是需要區別 Joe 和火焰的位置，故在節點上加入一個標記來區分。

當 Joe 到達迷宮的邊緣時，我們可以輸出他逃脫的時間，如果佇列被清空還沒找到逃脫路徑，則輸出 IMPOSSIBLE。

具體步驟如下：

1. 遍歷迷宮，將火焰的位置先加入佇列，並記錄 Joe 的位置。如果遇到火焰、Joe、牆壁，則標記為已訪問。
2. 使用佇列進行 BFS，每次取出一個節點，擴展其可到達範圍。
   • 節點中的資訊包含位置 $(x, y)$、是否為火焰、時間。
   • 若該節點為 Joe 且已經到達邊緣，則下一分鐘即可逃脫，輸出下一分鐘的時間。
   • 否則，擴展其可到達範圍，並將新的節點加入佇列。
3. 若佇列被清空還沒找到逃脫路徑，則輸出 IMPOSSIBLE。

複雜度分析

• 時間複雜度：$\mathcal{O}(R \times C)$，其中 $R$ 是迷宮的行數，$C$ 是列數。
  • 初始化標記時間複雜度為 $\mathcal{O}(R \times C)$。
  • BFS 時，由於只有未標記的格子才會被加入佇列，故每個網格最多被訪問一次，時間複雜度為 $\mathcal{O}(R \times C)$。
• 空間複雜度：$\mathcal{O}(R \times C)$，使用了一個 boolean 二維陣列 $vis$ 和一個佇列 $q$。

PythonC++

Python 範例程式碼無法通過 UVA 上的測試，會超時。

import sys
input = sys.stdin.readline
def print(val=""): sys.stdout.write(str(val) + "\n")

from collections import deque

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    grid = [list(input().strip()) for _ in range(n)]

    q = deque() # (i, j, is_fire, time)
    vis = [[False] * m for _ in range(n)] # visited
    for i, row in enumerate(grid):
        for j, ch in enumerate(row):
            if ch == '.': continue
            if ch == 'F':
                q.append((i, j, True, 0))
            elif ch == 'J': # Joe
                st = (i, j, False, 0)
            vis[i][j] = True

    ans = -1
    q.append(st)
    while q:
        x, y, is_fire, time = q.popleft()
        if not is_fire and (x == 0 or x == n - 1 or y == 0 or y == m - 1):
            ans = time + 1 # Joe escape at next time
            break
        for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny]:
                vis[nx][ny] = True
                q.append((nx, ny, is_fire, time + 1))
    print(ans if ans != -1 else "IMPOSSIBLE")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int DIR[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

class Node {
public:
    int x, y, time;
    bool is_fire;
    Node() {}
    Node (int x, int y, bool is_fire, int time) : x(x), y(y), is_fire(is_fire), time(time) {}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        vector<string> grid(n);
        for (int i = 0; i < n; i++) {
            cin >> grid[i];
        }
        Node st;
        queue<Node> q; // (i, j, is_fire, time)
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '.') continue;
                if (grid[i][j] == 'F') {
                    q.push({i, j, true, 0});
                } else if (grid[i][j] == 'J') {
                    st = {i, j, false, 0};
                }
                vis[i][j] = true;
            }
        }
        q.push(st);
        int ans = -1;
        while (!q.empty()) {
            Node node = q.front(); q.pop();
            int x = node.x, y = node.y, time = node.time;
            bool is_fire = node.is_fire;
            if (!is_fire && (x == 0 || x == n - 1 || y == 0 || y == m - 1)) {
                ans = time + 1;
                break;
            }
            for (int k = 0; k < 4; k++) {
                int nx = x + DIR[k][0], ny = y + DIR[k][1];
                if (0 <= nx && nx < n && 0 <= ny && ny < m && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.push({nx, ny, is_fire, time + 1});
                }
            }
        }
        cout << (ans != -1 ? to_string(ans) : "IMPOSSIBLE") << endl;
    }
    return 0;
}

---

寫在最後

Cover photo is remixed from @青爭, thanks for their work!