題目描述:給定一個 m × n 的二維網格,包含三種值:-1(牆壁,無法通行)、0(門)、2147483647(INF,代表空房間)。請將每個空房間的值更新為距離最近的門的距離。若無法到達任何門,則保持 INF 不變。
解題思路:與其從每個空房間出發用 BFS 找門(O((mn)²) 的暴力法),更有效率的做法是多源 BFS:同時從所有門(值為 0 的格子)出發,向外擴展。BFS 每擴展一層代表距離加一,當 BFS 波前抵達某個空房間時,記錄的距離就是最短距離,因為 BFS 保證最短路徑性質。只需將所有門加入初始佇列,同時進行 BFS 即可。
時間複雜度:O(m × n) — 每個格子最多被 BFS 訪問(入隊)一次,m 和 n 分別為網格的行數與列數。
空間複雜度:O(m × n) — 佇列最壞情況下容納所有空房間(無牆壁時)。
1. Initialize queue with all gate (0) positions
2. Define dirs = [up, down, left, right]
3. While queue not empty:
a. Dequeue cell (r, c)
b. For each neighbor (nr, nc) in 4 directions:
- If in bounds AND rooms[nr][nc] == INF:
* rooms[nr][nc] = rooms[r][c] + 1
* Enqueue (nr, nc)
4. (Rooms unreachable from any gate remain INF)從每個房間出發的 BFS O((mn)²):對每個 INF 格子做一次 BFS 找最近的門。正確但效率極差,在大型網格中難以通過。
Dijkstra O(mn log(mn)):將所有門的距離設為 0,其他格子設為 INF,跑最短路徑算法。由於邊權均為 1,Dijkstra 退化為 BFS,使用普通 BFS 即可,不需優先佇列。