286. Walls and Gates
題目給定一個矩陣，矩陣內有標記了牆與門，剩餘的點被標註成一個無限大的數值，意義為可以行走的點，要求把這些矩陣中除了門與牆以外的點，以該點到達附近最近的門的距離為何？
思路
為什麼不能照 1091 的做法
這個題目與 1091. Shortest Path in Binary Matrix 很類似，都是矩陣中有牆與路、要找出最短路線。在該題中，題目有設定好起點與終點的位置，所以可以使用廣度優先搜索的方式，逐步找出最短路徑。
雖然與 1091 題類似，但是我們不能使用 1091 的方法來做，因為這樣會使我們要遍歷每一個點後，才能完全證明所有的點都更新成了最短路徑的數值。而這樣的做法其實會有很多不必要的計算 —— 例如從 A 點到 B 點只有一條路線時，行經中間的點 k，其實已經知道它到 B 的最短路徑是「A 到 B 的距離減去 A 到 k 的距離」。
反過來，從門出發
所以這個題目可以反著做，直接從門出發，並且通過 BFS 的方式，逐步更新每個點與自己的距離。
一開始我把 BFS 的邏輯抽出來，對每個門各跑一次。但這樣會超時：第一個門探索的時候會跑到非常遠的地方，把所有能到的點都更新一遍；其他的門探索時，又會把這些點重新更新掉。門越多，重複的工就越多。
觀察題目，其實我們並不侷限一定要一個一個門的去探索。在實作 BFS 時，可以把所有的起點一同放在一起，多個點同時出發、同時一起探索，這樣速度會快很多。
為什麼多源 BFS 是對的
所有門一開始都在佇列裡、距離都是 0，於是 BFS 的波前齊步向外推進。這代表任何一格第一次被碰到的時候，就是經由離它最近的那個門 —— 不需要「先算一個值、之後再看能不能改小」，第一次寫進去的就是答案。
佇列裡的距離值變化可以驗證這件事（下面是 LeetCode 範例的實際追蹤）：
[0] → [0,1] → [1] → [1,2] → [2] → [2,3] → [3] → [3,4] → [4]
佇列裡永遠只同時存在兩個相鄰的距離值。 這是 FIFO 的保證：距離 d 的格子全部彈完，才會輪到 d+1。所以「一次 popleft 一個」不影響齊步性，波前確實是一起推進的。
牆是 -1，會自動被排除 —— 距離永遠 ≥ 0，所以 -1 > 任何距離 永遠不成立，不需要為牆寫任何特別判斷。
解題方向
每個門各自 BFS（會超時）
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def bfs(row, col):
queue = deque()
queue.append((row, col))
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nr = row + dr
nc = col + dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] > rooms[row][col] + 1:
rooms[nr][nc] = rooms[row][col] + 1
queue.append((nr, nc))
rows = len(rooms)
cols = len(rooms[0])
for row in range(rows):
for col in range(cols):
if rooms[row][col] == 0:
bfs(row, col)
多源 BFS
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
rows = len(rooms)
cols = len(rooms[0])
queue = deque()
for row in range(rows):
for col in range(cols):
if rooms[row][col] == 0:
queue.append((row, col)) # 所有門先全部入列
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nr = row + dr
nc = col + dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] > rooms[row][col] + 1:
rooms[nr][nc] = rooms[row][col] + 1
queue.append((nr, nc))
「多源」的全部意義就是進迴圈之前把所有起點都放進佇列，就是上面那個雙重迴圈。之後的 while 完全不用改。
補充
那個 + 1 不能少
條件寫成 rooms[nr][nc] > rooms[row][col]（少了 + 1）答案仍然正確，但會慢到跑不完。原因是：條件成立不代表值有改變，程式碼卻照樣把它重新入列。
假設彈出的格子距離是 d，看向的鄰居已經是 d + 1（別條路徑先算好的正確值）。這時 d + 1 > d 仍然成立，於是：
- 寫入
d + 1—— 值根本沒變，白做 - 但還是
queue.append—— 這格又被排進佇列一次
被重新入列的格子彈出時，又會對它的鄰居做同樣的事。於是每一條從門走到某格的最短路徑，都會各自觸發一次入列。3×3 全空、門在左上角，每格的入列次數會長成帕斯卡三角形：
| 5×5 每格的入列次數 | ||||
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | 5 |
| 1 | 3 | 6 | 10 | 15 |
| 1 | 4 | 10 | 20 | 35 |
| 1 | 5 | 15 | 35 | 70 |
那正是 ，也就是從門走到 (r, c) 的最短路徑條數。整張網格的總入列次數是 ：
| 網格（全空、一個門） | 少了 + 1 | 加上 + 1 |
|---|---|---|
| 4×4 | 69 | 16 |
| 8×8 | 12,869 | 64 |
| 12×12 | 2,704,155 | 144 |
| 14×14 | > 5,000,000 | 196 |
加上 + 1 之後，鄰居剛好是 d + 1 時 d + 1 > d + 1 為 false，直接跳過，每格只會入列一次。
一句話記住差別：原本的條件在問「這格有沒有比我遠？」，該問的是「這格能不能因為經過我而變得更近？」。
while 搭配 for 的那種寫法呢
那是另一件事，和「多源」無關。差別在於需不需要一個外部的層數計數器：
| 距離存在哪裡 | 要不要 for _ in range(len(queue)) | |
|---|---|---|
| 286 這題 | 寫進 rooms 格子裡，讀 rooms[row][col] + 1 就有 | 不需要 |
| 994. Rotting Oranges | 要回傳「幾分鐘」，沒有地方存 | 需要，用外層迴圈數層數 |
| 102. Binary Tree Level Order Traversal | 要每層一個陣列 | 需要，用它切分層 |
兩種寫法對這題的結果完全相同。會混淆多半是因為看過 994 那種寫法 —— 那題非用 for 不可，但理由是要數分鐘，不是為了「同時出發」。
相關題目
994. Rotting Oranges 是最接近的多源 BFS 題；200. Number of Islands 是同樣的網格骨架但不需要距離；1091. Shortest Path in Binary Matrix 是單一起點終點的版本。骨架見 BFS / DFS 模板。
複雜度
多源 BFS（正確版）
- 時間 — 每一格最多入列、出列各一次
- 空間 — 佇列最壞情況；一開始就把所有門放進去，門可能佔滿整張網格
每個門各自 BFS
- 時間 —
g是門的數量，每個門都可能掃過整張網格 - 空間
少了 + 1 的版本
- 時間指數級 — 入列次數是 ，12×12 就要 270 萬次
其中 m、n 是網格的列數和行數，g 是門的數量。距離直接寫在 rooms 裡，所以沒有額外的距離陣列。