题目描述
思路解析动画文字版
记住「从入口一圈圈扩、入队即标记、第一次踩到边界空地即最近出口」,下面逐帧套它。
迷宫最近出口：入口 (1,1)(紫)入队,步数 0,并标记为已访问(以后不再走它)。规则:出口必须是边界上的空地、且不能是入口本身。开始一圈圈往外扩。
迷宫最近出口：弹出队首 (1,1)(紫,步数 0)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (2,1)、(1,2)(高亮)标记已访问、带步数 1 入队。(1,1) 处理完转蓝。
迷宫最近出口：弹出队首 (2,1)(紫,步数 1)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (3,1)、(2,2)(高亮)标记已访问、带步数 2 入队。(2,1) 处理完转蓝。
迷宫最近出口：弹出队首 (1,2)(紫,步数 1)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (1,3)(高亮)标记已访问、带步数 2 入队。(1,2) 处理完转蓝。
迷宫最近出口：弹出队首 (3,1)(紫,步数 2)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (3,2)(高亮)标记已访问、带步数 3 入队。(3,1) 处理完转蓝。
迷宫最近出口：弹出队首 (2,2)(紫,步数 2)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (2,3)(高亮)标记已访问、带步数 3 入队。(2,2) 处理完转蓝。
迷宫最近出口：弹出队首 (1,3)(紫,步数 2)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (1,4)(高亮)标记已访问、带步数 3 入队。(1,3) 处理完转蓝。
迷宫最近出口：弹出队首 (3,2)(紫,步数 3)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (3,3)(高亮)标记已访问、带步数 4 入队。(3,2) 处理完转蓝。
迷宫最近出口：弹出队首 (2,3)(紫,步数 3)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (2,4)(高亮)标记已访问、带步数 4 入队。(2,3) 处理完转蓝。
迷宫最近出口：弹出队首 (1,4)(紫,步数 3)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (1,5)(高亮)标记已访问、带步数 4 入队。(1,4) 处理完转蓝。
迷宫最近出口：弹出队首 (3,3)(紫,步数 4)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (3,4)(高亮)标记已访问、带步数 5 入队。(3,3) 处理完转蓝。
迷宫最近出口：弹出队首 (2,4)(紫,步数 4)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (2,5)(高亮)标记已访问、带步数 5 入队。(2,4) 处理完转蓝。
迷宫最近出口：弹出队首 (1,5)(紫,步数 4)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：(1,5) 四周没有新的可走空地,处理完转蓝。
迷宫最近出口：弹出队首 (3,4)(紫,步数 5)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：把能走的新空地 (3,5)(高亮)标记已访问、带步数 6 入队。(3,4) 处理完转蓝。
迷宫最近出口：弹出队首 (2,5)(紫,步数 5)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：(2,5) 四周没有新的可走空地,处理完转蓝。
迷宫最近出口：弹出队首 (3,5)(紫,步数 6)。看它上下左右四个方向,能走的空地准备入队。
迷宫最近出口：往下的 (4,5) 是边界上的空地,这就是最近出口!当前步数 6 再加这一步 = 7,就是答案。
迷宫最近出口：沿「从谁来的」回溯,绿色就是入口到最近出口的最短路,一共 7 步。BFS 按步数逐层扩散,所以第一次碰到边界出口时的步数,一定是最近的。
边界:相邻出口 1 步;封死 −1;入口在边界也不算出口。
两个延伸:可多源 BFS 从边界反推;原地改格省空间。
参考代码
from typing import Listfrom collections import dequeclass Solution: def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int: maze = [list(row) for row in maze] m, n = len(maze), len(maze[0]) sr, sc = entrance q = deque([(sr, sc, 0)]) maze[sr][sc] = '+' while q: r, c, d = q.popleft() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.': if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1: return d + 1 maze[nr][nc] = '+' q.append((nr, nc, d + 1)) return -1复杂度
- 时间：O(mn)，每个格子最多入队一次、出队一次,各看四个方向,共 O(mn)
- 空间：O(mn)，队列与访问标记最坏装下整张迷宫,O(mn)
易错点
面试追问把动画讲成自己的话
追问能不能从四条边界的所有空地反过来做多源 BFS?
追问如果迷宫非常大、内存吃紧怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
到达目的地的方案数
LeetCode 1976 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题