LeetCode 题解工作台
迷宫中离入口最近的出口
给你一个 m x n 的迷宫矩阵 maze （ 下标从 0 开始 ），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrance row , entrance col ] 表示你一开始所在格子的行和列。 每一步操作…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以从入口开始，进行广度优先搜索，每次搜索到一个新的空格子，就将其标记为已访问，并将其加入队列，直到找到一个边界上的空格子，返回步数。 具体地，我们定义一个队列 ，初始时我们将 加入队列。定义一个变量 记录步数，初始为 。然后我们开始进行广度优先搜索，每一轮我们取出队列中的所有元素，遍历这些元素，对于每个元素，我们尝试向四个方向移动，如果移动后的位置是一个空格子，我们将其加入队列，并将其标…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
示例 1：
输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] 输出：1 解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。 一开始，你在入口格子 (1,2) 处。 - 你可以往左移动 2 步到达 (1,0) 。 - 你可以往上移动 1 步到达 (0,2) 。 从入口处没法到达 (2,3) 。 所以，最近的出口是 (0,2) ，距离为 1 步。
示例 2：
输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] 输出：2 解释：迷宫中只有 1 个出口，在 (1,2) 处。 (1,0) 不算出口，因为它是入口格子。 初始时，你在入口与格子 (1,0) 处。 - 你可以往右移动 2 步到达 (1,2) 处。 所以，最近的出口为 (1,2) ，距离为 2 步。
示例 3：
输入：maze = [[".","+"]], entrance = [0,0] 输出：-1 解释：这个迷宫中没有出口。
提示：
maze.length == mmaze[i].length == n1 <= m, n <= 100maze[i][j]要么是'.'，要么是'+'。entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrance一定是空格子。
解题思路
方法一：BFS
我们可以从入口开始，进行广度优先搜索，每次搜索到一个新的空格子，就将其标记为已访问，并将其加入队列，直到找到一个边界上的空格子，返回步数。
具体地，我们定义一个队列 ，初始时我们将 加入队列。定义一个变量 记录步数，初始为 。然后我们开始进行广度优先搜索，每一轮我们取出队列中的所有元素，遍历这些元素，对于每个元素，我们尝试向四个方向移动，如果移动后的位置是一个空格子，我们将其加入队列，并将其标记为已访问。如果移动后的位置是边界上的空格子，我们返回 。如果队列为空，我们返回 。这一轮搜索结束后，我们将 加一，继续进行下一轮搜索。
遍历结束后，如果我们没有找到边界上的空格子，我们返回 。
时间复杂度 ，空间复杂度 。其中 和 分别是迷宫的行数和列数。
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
m, n = len(maze), len(maze[0])
i, j = entrance
q = deque([(i, j)])
maze[i][j] = "+"
ans = 0
while q:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and maze[x][y] == ".":
if x == 0 or x == m - 1 or y == 0 or y == n - 1:
return ans
q.append((x, y))
maze[x][y] = "+"
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n) because each cell is visited at most once during BFS. Space complexity is O(m_ n) for the queue and visited markers, proportional to the maze size. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask about edge cases where the entrance is on the boundary.
- question_mark
Expect discussion on why BFS guarantees the shortest path compared to DFS.
- question_mark
Be ready to explain how marking visited cells prevents infinite loops in the traversal.
常见陷阱
外企场景- error
Treating the entrance as an exit accidentally when it is on the border.
- error
Forgetting to check bounds before accessing neighboring cells.
- error
Using DFS which may find a longer path and fail on minimal steps requirement.
进阶变体
外企场景- arrow_right_alt
Find the longest path from entrance to any exit using BFS levels differently.
- arrow_right_alt
Return all exits reachable with the minimum number of steps.
- arrow_right_alt
Modify the maze to include weighted steps and use BFS with priority queue.