题目描述
先确认输入、输出、限制条件，再判断能不能把暴力解法优化掉。
思路解析动画文字版
关键转折：别一个房间一个房间去搜门。反过来：从所有门一起出发，像水波一样一圈圈往外漫。空房间第一次被波纹碰到，那一刻的层数就是它到最近门的最短距离。
第 0 层 · 所有门一起入队：把全部 2 个门 (3,0)、(3,3) 一次性放进队列，它们都算「第 0 层」。墙 (0,1)、(2,1)、(2,3) 是灰色障碍，水波绕着走。11 个 ∞ 空房间等着被波纹碰到。
波纹扩散 · 碰到空房间 (2,0)：波纹从已知格 (3,0) 往邻居 (2,0) 漫一步。这是空房间 (2,0) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 1，以后不再更新。
落子 · (2,0) = 1：给 (2,0) 填上 1，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (3,1)：波纹从已知格 (3,0) 往邻居 (3,1) 漫一步。这是空房间 (3,1) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 1，以后不再更新。
落子 · (3,1) = 1：给 (3,1) 填上 1，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (3,2)：波纹从已知格 (3,3) 往邻居 (3,2) 漫一步。这是空房间 (3,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 1，以后不再更新。
落子 · (3,2) = 1：给 (3,2) 填上 1，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (1,0)：波纹从已知格 (2,0) 往邻居 (1,0) 漫一步。这是空房间 (1,0) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 2，以后不再更新。
落子 · (1,0) = 2：给 (1,0) 填上 2，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (2,2)：波纹从已知格 (3,2) 往邻居 (2,2) 漫一步。这是空房间 (2,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 2，以后不再更新。
落子 · (2,2) = 2：给 (2,2) 填上 2，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (0,0)：波纹从已知格 (1,0) 往邻居 (0,0) 漫一步。这是空房间 (0,0) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 3，以后不再更新。
落子 · (0,0) = 3：给 (0,0) 填上 3，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (1,1)：波纹从已知格 (1,0) 往邻居 (1,1) 漫一步。这是空房间 (1,1) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 3，以后不再更新。
落子 · (1,1) = 3：给 (1,1) 填上 3，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (1,2)：波纹从已知格 (2,2) 往邻居 (1,2) 漫一步。这是空房间 (1,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 3，以后不再更新。
落子 · (1,2) = 3：给 (1,2) 填上 3，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (0,2)：波纹从已知格 (1,2) 往邻居 (0,2) 漫一步。这是空房间 (0,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 4，以后不再更新。
落子 · (0,2) = 4：给 (0,2) 填上 4，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (1,3)：波纹从已知格 (1,2) 往邻居 (1,3) 漫一步。这是空房间 (1,3) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 4，以后不再更新。
落子 · (1,3) = 4：给 (1,3) 填上 4，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹扩散 · 碰到空房间 (0,3)：波纹从已知格 (0,2) 往邻居 (0,3) 漫一步。这是空房间 (0,3) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 5，以后不再更新。
落子 · (0,3) = 5：给 (0,3) 填上 5，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
波纹漫完 · 每个空房间都有了最近距离：队列空了，水波漫遍所有能到的房间。每个 ∞ 都换成了到最近门的最短步数。要是某个房间被墙完全围死、波纹到不了，它就一直留着 ∞（本例没有这种死角）。
边界：空矩阵直接返回；全是墙或全是门时队列里没有 ∞ 可填；有房间被墙围死走不到门，留 ∞ 是对的，不要强行填。
高频追问：问：为什么从门往外搜而不是从房间搜门？答：门可能有很多个，多源 BFS 一次漫完所有房间，而从每个房间各搜一次门会重复劳动。问：怎么保证是最短？答：BFS 按层扩，第一次到达即最短。
参考代码
def wallsAndGates(rooms): if not rooms: return R, C = len(rooms), len(rooms[0]) from collections import deque q = deque((i, j) for i in range(R) for j in range(C) if rooms[i][j] == 0) while q: i, j = q.popleft() for di, dj in ((1,0),(-1,0),(0,1),(0,-1)): ni, nj = i + di, j + dj if 0 <= ni < R and 0 <= nj < C \ and rooms[ni][nj] == 2147483647: rooms[ni][nj] = rooms[i][j] + 1 q.append((ni, nj))复杂度
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
课程表
LeetCode 207 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题