286. Walls and Gates
這題是 BFS 廣度優先搜索的題目，DFS 應該也可以做。
我一開始的做法是把 BFS 的邏輯抽出來寫如下，但是這樣做會超時，因為其實這樣做除了 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]:
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)
不過其實這題稍微特別一點，可以把所有的出發地點都先放進去 queue ，同時一起探索，這樣的話速度會快很多。
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]:
rooms[nr][nc] = rooms[row][col] + 1
queue.append((nr, nc))