---
title: "286. Walls and Gates"
url: "https://laigary.com/interview/coding/286-walls-and-gates"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Graph", "Breadth-First Search"]
---

# 286. Walls and Gates

[286\. Walls and Gates](https://leetcode.com/problems/walls-and-gates/)

題目給定一個矩陣，矩陣內有標記了牆與門，剩餘的點被標註成一個無限大的數值，意義為可以行走的點，要求把這些矩陣中除了門與牆以外的點，以該點到達附近最近的門的距離為何？

## 思路

### 為什麼不能照 1091 的做法

這個題目與 [1091\. Shortest Path in Binary Matrix](/interview/coding/1091-shortest-path-in-binary-matrix) 很類似，都是矩陣中有牆與路、要找出最短路線。在該題中，題目有設定好起點與終點的位置，所以可以使用廣度優先搜索的方式，逐步找出最短路徑。

雖然與 1091 題類似，但是我們不能使用 1091 的方法來做，因為這樣會使我們要遍歷每一個點後，才能完全證明所有的點都更新成了最短路徑的數值。而這樣的做法其實會有很多不必要的計算 —— 例如從 A 點到 B 點只有一條路線時，行經中間的點 `k`，其實已經知道它到 B 的最短路徑是「A 到 B 的距離減去 A 到 k 的距離」。

### 反過來，從門出發

所以這個題目可以反著做，直接從門出發，並且通過 BFS 的方式，逐步更新每個點與自己的距離。

一開始我把 BFS 的邏輯抽出來，對每個門各跑一次。但這樣會超時：第一個門探索的時候會跑到非常遠的地方，把所有能到的點都更新一遍；其他的門探索時，又會把這些點重新更新掉。門越多，重複的工就越多。

觀察題目，其實我們並不侷限一定要一個一個門的去探索。在實作 BFS 時，可以把**所有的起點一同放在一起**，多個點同時出發、同時一起探索，這樣速度會快很多。

### 為什麼多源 BFS 是對的

所有門一開始都在佇列裡、距離都是 0，於是 BFS 的波前**齊步向外推進**。這代表任何一格**第一次被碰到的時候，就是經由離它最近的那個門** —— 不需要「先算一個值、之後再看能不能改小」，第一次寫進去的就是答案。

佇列裡的距離值變化可以驗證這件事（下面是 LeetCode 範例的實際追蹤）：

```text
[0] → [0,1] → [1] → [1,2] → [2] → [2,3] → [3] → [3,4] → [4]
```

**佇列裡永遠只同時存在兩個相鄰的距離值。** 這是 FIFO 的保證：距離 `d` 的格子全部彈完，才會輪到 `d+1`。所以「一次 `popleft` 一個」不影響齊步性，波前確實是一起推進的。

**牆是 `-1`，會自動被排除** —— 距離永遠 ≥ 0，所以 `-1 > 任何距離` 永遠不成立，不需要為牆寫任何特別判斷。

## 解題方向

### 每個門各自 BFS（會超時）

```python
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

```python
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** |

那正是 $\binom{r+c}{r}$，也就是從門走到 `(r, c)` 的最短路徑條數。整張網格的總入列次數是 $\binom{2n}{n} - 1$：

| 網格（全空、一個門） | 少了 `+ 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](/interview/coding/994-rotting-oranges) | 要回傳「幾分鐘」，沒有地方存 | **需要**，用外層迴圈數層數 |
| [102. Binary Tree Level Order Traversal](/interview/coding/102-binary-tree-level-order-traversal) | 要每層一個陣列 | **需要**，用它切分層 |

兩種寫法對這題的結果完全相同。會混淆多半是因為看過 994 那種寫法 —— 那題非用 `for` 不可，但理由是要數分鐘，不是為了「同時出發」。

### 相關題目

[994. Rotting Oranges](/interview/coding/994-rotting-oranges) 是最接近的多源 BFS 題；[200. Number of Islands](/interview/coding/200-number-of-islands) 是同樣的網格骨架但不需要距離；[1091. Shortest Path in Binary Matrix](/interview/coding/1091-shortest-path-in-binary-matrix) 是單一起點終點的版本。骨架見 [BFS / DFS 模板](/interview/coding/bfs-dfs-template)。

## 複雜度

**多源 BFS（正確版）**
- 時間 $O(mn)$ — 每一格最多入列、出列各一次
- 空間 $O(mn)$ — 佇列最壞情況；一開始就把所有門放進去，門可能佔滿整張網格

**每個門各自 BFS**
- 時間 $O(g \cdot mn)$ — `g` 是門的數量，每個門都可能掃過整張網格
- 空間 $O(mn)$

**少了 `+ 1` 的版本**
- 時間**指數**級 — 入列次數是 $\binom{2n}{n} - 1$，12×12 就要 270 萬次

其中 `m`、`n` 是網格的列數和行數，`g` 是門的數量。距離直接寫在 `rooms` 裡，所以沒有額外的距離陣列。