LeetCode 286. 墙与门

2023-10-28 HGNULB 约 14 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 286. 墙与门

题意分析

给一个 m × n 的网格 rooms，每格是三种值之一：-1 表示墙（不可通行）、0 表示门、2147483647（即 INF）表示空房间。要求就地把每个空房间改成「到最近的门的最短距离」，走不到任何门的房间保持 INF 不变。只能上下左右四向移动，每步距离为 1。

「最近的门」意味着这是一个最短路问题；「每步距离为 1」意味着边权全部相等，这一条是全题最强的信号——边权为 1 的最短路用 BFS 就够，不需要 Dijkstra。

但要注意方向。题目问的是「每个房间到最近的门」，而门可能有很多个。如果按字面从每个房间出发去找门，就要跑 $O(mn)$ 次 BFS；反过来从门出发向外扩散，每个房间被扩散到的时刻恰好就是它到最近门的距离——把「多个终点、单个起点」反转成「多个起点、单个终点」，是这类题的标准视角切换。

输入的取值编码也在暗示做法。INF 用的是 Integer.MAX_VALUE，正好是「未访问」的天然标记：只要一个格子还等于 INF，就说明它既不是墙、也不是门、也还没被赋过距离。这让我们可以省掉单独的 visited 数组，直接拿 rooms 本身当访问标记。

返回值是 void，要求原地修改，所以不能另开一个距离矩阵再拷回去（虽然那样也对，但白白多用 $O(mn)$ 空间）。

边界有四处：网格为空或行为空时直接返回；一个门都没有时所有 INF 保持不变；被墙完全围死的房间同样保持 INF；门本身的值是 0，不需要也不能被改写。

解法：多源 BFS

核心思路

朴素做法是对每个空房间单独跑一次 BFS 去找最近的门。正确，但每次 BFS 都是 $O(mn)$，总共 $O((mn)^2)$，在 250 × 250 的网格上就是约 $4 \times 10^9$ 次操作，超时。瓶颈在于：同一片区域被反复遍历了成千上万遍，而每次遍历得到的信息（哪些格子离哪些门多远）被完全丢弃。

关键观察是把搜索方向倒过来。距离是对称的：房间 A 到门 G 的最短步数，等于门 G 到房间 A 的最短步数。所以与其从每个房间找门，不如从所有门同时出发向外扩散，谁先被扩散到，谁就离某个门更近。

「所有门同时出发」在 BFS 里的实现方式，就是把全部门在初始化阶段一次性推进队列，这称为多源 BFS。它和单源 BFS 的唯一区别只在初始队列的规模——可以想象存在一个虚拟超级源点，向每个门连一条权为 0 的边，那么从超级源点做单源 BFS 时，第一层弹出的正好是全部门。所以多源 BFS 的正确性完全继承自单源 BFS，不需要额外论证。

于是显式写出这个算法维持的不变量：队列中所有格子的距离值至多相差 1，且按非降序排列；任何一个已经被赋过距离值的格子，其值就是它到最近门的真实最短距离，之后不再改变。初始时队列里全是距离 0 的门，不变量成立；每次从队首弹出距离为 d 的格子，把它未访问的邻居赋成 d + 1 并推入队尾，队列仍保持非降序且极差不超过 1。

「首次访问即最短」这个结论正是由不变量推出的：由于队列按距离非降序出队，一个格子第一次被某个邻居扩散到时，那个邻居的距离已经是当前全局最小的一档，不可能存在更短的路径后来才被发现。所以赋值必须发生在入队时刻，且赋过一次就不再更新。

访问标记的处理是本题的巧妙之处。判断条件写成 rooms[nr][nc] != INF 就 continue，一句话同时挡掉了三种格子：墙（-1）、门（0）、已经被赋过距离的房间（正整数）。不需要单独的 visited 数组，也不需要三个分支——因为「值仍等于 INF」和「是尚未访问的空房间」在这道题里完全等价。

走不到的房间自动保持 INF：它们永远不会进入队列，也就永远不会被赋值，正是题目要的结果。同样地，没有门时初始队列为空，循环一次都不执行，全网格原样返回。这两个边界都不需要特判。

解题步骤

取出 m、n 并处理空网格：m == 0 时直接返回。为什么必须先判——下一行要读 rooms[0].length，空数组会越界。

扫描全网格，把所有值为 0 的格子推入队列：为什么是「所有」而不是找到第一个就开始——多源 BFS 的正确性依赖于「所有源点同处第 0 层」，漏掉任何一个门都会让它附近的房间被别的更远的门错误地占据。

不把门标记成已访问也不改写门的值：门本身已经是 0，而后续的 != INF 判断天然会跳过它，所以不需要额外处理。

准备四方向偏移数组 dr、dc：为什么用偏移数组而不是写四段重复代码——一是短，二是把「四向」这个参数抽出来，改成八向时只需扩数组。

循环：队列非空时弹出队首 (r, c)：为什么用队列而不是栈——BFS 要求按距离分层推进，栈会变成 DFS，首次访问不再保证最短。

对四个邻居先判越界再判可访问性：nr、nc 越界就跳过；rooms[nr][nc] != INF 就跳过。为什么越界判断必须排在取值之前——顺序反了会先读到界外内存直接抛异常。

赋值 rooms[nr][nc] = rooms[r][c] + 1 并立即入队：为什么赋值要在入队的同一时刻完成——赋值同时承担了「记录距离」和「标记已访问」两个职责；若推迟到出队时再赋值，同一个格子可能被多个邻居重复入队，队列规模膨胀且可能被更远的路径覆盖。

循环自然结束后返回：为什么不需要收尾——所有可达房间都已被赋值，不可达的仍是 INF，正是题目要求的最终状态。

以下面这个 4 × 4 网格走一遍（I 代表 INF）：

[[I, -1, 0, I], [I, I, I, -1], [I, -1, I, -1], [0, -1, I, I]]

初始化扫描：值为 0 的格子有 (0,2) 和 (3,0) 两个门，都入队。队列 [(0,2), (3,0)]，这是第 0 层，距离都是 0。

第 1 层扩散：弹出 (0,2)，四个邻居中 (1,2) 是 INF，赋 0 + 1 = 1 并入队；(0,1) 是墙跳过；(0,3) 是 INF，赋 1 入队；上方越界。弹出 (3,0)，邻居 (2,0) 是 INF，赋 1 入队；(3,1) 是墙；下方与左方越界。本层新增 (1,2)=1、(0,3)=1、(2,0)=1。

第 2 层：弹出 (1,2)，邻居 (2,2) 是 INF 赋 2 入队，(0,2) 是门（值 0，不等于 INF）跳过，(1,3) 是墙，(1,1) 是 INF 赋 2 入队。弹出 (0,3)，邻居 (1,3) 是墙，(0,2) 是门跳过。弹出 (2,0)，邻居 (1,0) 是 INF 赋 2 入队，(3,0) 是门跳过，(2,1) 是墙。本层新增 (2,2)=2、(1,1)=2、(1,0)=2。

注意 (1,0) 这一格：它同时是 (1,1) 和 (2,0) 的邻居，但因为 (2,0) 先出队，它被赋值为 2 后立刻不再等于 INF，随后 (1,1) 再来扩散时会被 != INF 挡住，不会被重复赋值也不会重复入队——这正是「赋值即标记」的作用。

第 3 层：弹出 (2,2)，邻居 (3,2) 赋 3 入队；(1,2) 已有值跳过，左右都是墙。弹出 (1,1)，邻居 (0,1) 是墙，(2,1) 是墙，(1,0) 已有值，(1,2) 已有值。弹出 (1,0)，邻居 (0,0) 是 INF 赋 3 入队，(2,0) 已有值，(1,1) 已有值。本层新增 (3,2)=3、(0,0)=3。

第 4 层：弹出 (3,2)，邻居 (3,3) 是 INF 赋 4 入队，(2,2) 已有值，(3,1) 是墙。弹出 (0,0)，邻居全是墙、已有值或越界。本层新增 (3,3)=4。

第 5 层：弹出 (3,3)，四个邻居分别是墙、已有值或越界，无新增。队列变空，循环结束。

最终网格：

[[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

验证几个有代表性的格子。(0,0) 的值是 3：它到门 (0,2) 被 (0,1) 的墙挡住，只能绕行 (0,0) → (1,0) → (1,1) → (1,2) → (0,2)，是 4 步；而到门 (3,0) 是 (0,0) → (1,0) → (2,0) → (3,0)，3 步，更近，答案取 3，正确。(3,3) 的值是 4：唯一通路是 (3,3) → (3,2) → (2,2) → (1,2) → (0,2)，恰好 4 步。若改用单源 BFS 只从 (0,2) 出发，(0,0) 会被算成 4，正是「必须所有门同时入队」的直接证据。

代码实现

// 遇到墙（-1）跳过，只对值为 INF 的空房间更新距离。
import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length;
        if (m == 0) {
            return;
        }
        int n = rooms[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (rooms[r][c] == 0) {
                    queue.offer(new int[]{r, c});
                }
            }
        }

        int[] dr = new int[]{1, -1, 0, 0};
        int[] dc = new int[]{0, 0, 1, -1};
        int INF = 2147483647;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }
                if (rooms[nr][nc] != INF) {
                    continue;
                }
                rooms[nr][nc] = rooms[r][c] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}

// 遇到墙（-1）跳过，只对值为 INF 的空房间更新距离。
func wallsAndGates(rooms [][]int) {
	m := len(rooms)
	if m == 0 {
		return
	}
	n := len(rooms[0])
	type pair struct{ r, c int }

	queue := make([]pair, 0)
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if rooms[r][c] == 0 {
				queue = append(queue, pair{r: r, c: c})
			}
		}
	}

	dr := []int{1, -1, 0, 0}
	dc := []int{0, 0, 1, -1}
	const INF = 2147483647

	head := 0
	for head < len(queue) {
		cur := queue[head]
		head++
		for k := 0; k < 4; k++ {
			nr := cur.r + dr[k]
			nc := cur.c + dc[k]
			if nr < 0 || nr >= m || nc < 0 || nc >= n {
				continue
			}
			if rooms[nr][nc] != INF {
				continue
			}
			rooms[nr][nc] = rooms[cur.r][cur.c] + 1
			queue = append(queue, pair{r: nr, c: nc})
		}
	}
}

复杂度分析

时间复杂度：$O(m \cdot n)$。凭什么：初始化要扫一遍全网格找门，是 $O(mn)$；BFS 阶段每个格子最多入队一次——因为赋值与入队同时发生，赋值后它不再等于 INF，后续任何扩散都会被 != INF 挡住——所以出队总次数不超过 $mn$，每次出队固定检查 4 个邻居，是常数工作量。合计 $O(mn)$，与门的数量无关。

空间复杂度：$O(m \cdot n)$。距离直接写回 rooms，不需要距离矩阵或 visited；额外空间来自队列。全是门或某一层包含大量格子时，队列都可能达到 $O(mn)$，不能把一般上界降成某个边长。

关键点总结

边权全为 1 的最短路一律用 BFS，不要上 Dijkstra——BFS 的分层出队顺序已经天然实现了「按距离递增处理」，堆是多余的 $\log$ 因子。

遇到「每个点到最近的某类特殊点」，把搜索方向反转成「从所有特殊点同时出发」，一次多源 BFS 替代 $O(mn)$ 次单源 BFS。这是本题最核心的可迁移思想，542、994、1162 全是同一个模子。

多源 BFS 的正确性可以用「虚拟超级源点连 0 权边」来解释，不必重新证明；面试中说出这个等价视角比说「因为都是 0 层」更有说服力。

赋值必须发生在入队时刻，不能推迟到出队时。这是 BFS 去重的通用铁律：入队即标记保证每个点只入队一次；出队才标记会让同一个点被多个前驱重复入队，最坏退化成指数规模。

善用输入本身的取值编码当访问标记（这里 INF 同时表示「空房间」和「未访问」），能省掉整个 visited 数组。前提是要确认这个编码不会与合法距离值冲突——本题距离最大不超过 $mn$，远小于 INF，安全。

「不可达」不需要特判：不可达的格子永远不会入队，自然保持初值。让边界情况自然落入主逻辑而不是靠 if 兜住，是实现质量的标志。

面试视角：这题的分水岭是能否第一时间说出「从门出发而不是从房间出发」。回答顺序建议是：先说朴素的每房间 BFS 及其 $O((mn)^2)$ 瓶颈，再点出距离对称性与方向反转，然后说明多源初始化，最后强调入队即赋值。被追问空间优化时，要能指出「用 INF 当访问标记省掉 visited」这一点。

面试视角：常见追问是「如果每步代价不同（比如有沼泽地格子走一步要 2）怎么办」。要能立刻答出退化为多源 Dijkstra，把队列换成按距离排序的优先队列，正确性依据从「出队顺序非降」变成「堆顶最小」。

易错点总结

只把第一个找到的门入队，或对每个门分别跑一次 BFS 并取 min：用例 [[I,-1,0,I],[I,I,I,-1],[I,-1,I,-1],[0,-1,I,I]]，只从 (0,2) 出发会把 (0,0) 算成 4，而它到门 (3,0) 只要 3 步，正确答案是 3。

把赋值推迟到出队时才做：用例 [[0,I,I],[I,I,I],[I,I,0]]，格子 (1,1) 会同时被 (0,1) 和 (1,0) 扩散并两次入队，队列规模膨胀；更糟的是若后来者的距离更大，出队时会把已经正确的 2 覆盖成 3。

把所有门压栈后按 DFS 首次访问即定值：用例 [[0,I,I,I,I,0]] 若后压入右侧门，DFS 会先从右向左把第二格写成 4；之后左侧门再处理时该格已被标记，无法改成正确距离 1。首次访问即最短只属于按层扩展的 BFS。

跳过条件写成 rooms[nr][nc] == -1 只挡墙：用例 [[0,I],[I,I]]，格子 (0,1) 被赋 1 后还会被 (1,1) 再次访问并赋成 3，同时无限重复入队，程序陷入死循环或超时。

跳过条件漏掉门：用例 [[0,I,0]]，若只判「不是墙且不是已赋值房间」而没排除值为 0 的门，门 (0,2) 会被 (0,1) 扩散成 2，门的值被破坏，题目要求门保持 0。

先取值后判越界：用例 [[0]]，扩展 (0,-1) 时先执行 rooms[0][-1] 直接抛越界异常（Go 版 panic），必须把边界检查排在数组访问之前。

额外开一个距离矩阵而不原地修改：用例任意网格，函数返回 void 而调用方检查的是 rooms 本身，写到临时矩阵里而忘记拷回，rooms 完全没变，全部用例失败。

把 INF 写成自定义的较小值（如 1000000）去比较：用例 [[2147483647]]，输入里的实际值是 2147483647，与自定义常量不相等，这个空房间会被当成「已访问」而永远不被扩散，本该保持 INF 的碰巧对了，但一旦它可达就会漏算。

给没有门的网格加特判返回全 0 或抛错：用例 [[I,I],[I,-1]]，正确行为是原样返回全 INF；主逻辑本就能处理（初始队列为空、循环不执行），加特判反而制造错误。

误以为被墙围死的房间需要显式赋值：用例 [[0,-1,I]]，(0,2) 不可达应保持 2147483647，若在收尾时把所有仍为 INF 的格子改成 -1 或 0 都是错的。

距离用 rooms[r][c] + 1 却在 rooms[r][c] 仍是 INF 时执行：这种情况只会在门未被正确识别时发生，用例 [[0,I]] 中若把 (0,1) 误当成源点入队，2147483647 + 1 会溢出成负数，后续距离全部为负。

多源初始化时只扫了部分行列（如把 n 写成 rooms.length）：用例 [[0,I,I,I],[I,I,I,I]]（m=2、n=4），把列数误当成 2 会漏扫 (0,2)、(0,3)、(1,2)、(1,3)，若其中有门则该门附近的房间距离全部偏大。

相似题目

题目	难度	考察点
542. 01 矩阵	中等	与本题几乎同构，源点是所有 0，考察是否需要额外 `visited`（值域含 0 会冲突）
994. 腐烂的橘子	中等	求的是全部染完所需层数而非逐点距离，需要显式按层推进并判断是否有剩余
1162. 地图分析	中等	求的是所有海洋中距陆地最远的那个，即多源 BFS 结果的最大值，要处理全陆或全海
200. 岛屿数量	中等	只需连通性不需要距离，DFS 与 BFS 皆可，用来对照「何时不必分层」
130. 被围绕的区域	中等	从边界多源出发做反向标记，考察「先标记安全区再统一改写」的补集思路
505. 迷宫 II	中等	球滚到墙才停使得边权不再为 1，BFS 失效，必须换 Dijkstra
1091. 二进制矩阵中的最短路径	中等	八向移动的单源 BFS，考察方向数组扩展与起点终点重合的边界
127. 单词接龙	困难	把 BFS 从网格搬到隐式图上，邻接关系需要现场构造，考察建图与去重