LeetCode 1926. 迷宫中离入口最近的出口

2026-07-14 HGNULB 约 13 分钟

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

分类

题目描述

✅ 1926. 迷宫中离入口最近的出口

题意分析

给定一个 m x n 的字符矩阵 maze，'.' 表示空格（可以走），'+' 表示墙（不能走），再给定入口坐标 entrance = [row, col]，保证入口一定是空格。每一步可以向上、下、左、右移动一格，不能穿墙也不能走出矩阵。要求返回从入口走到最近的出口所需的最少步数，走不到任何出口时返回 -1。

这里的「出口」有精确定义：位于迷宫边界上的空格，并且不是入口本身。边界指第 0 行、第 m - 1 行、第 0 列、第 n - 1 列这四条边上的格子。

第一个关键信号是「最少步数」加上「每步移动一格」。所有移动的代价完全相同，也就是说这是一张无权图上的最短路问题。在等权图里，从起点出发一圈一圈地向外扩展，第 k 圈里的格子恰好就是距入口 k 步的全部格子；只要按圈的顺序推进，第一次碰到出口时的圈号就是答案，不需要也不应该去枚举所有路径。这是后面整套写法成立的唯一依据，也是与「带权最短路」题目的分界线：一旦每步代价不同，圈的顺序就不再等于距离的顺序。

第二个关键信号是「入口本身不算出口」。这一条极容易漏掉，而且漏掉之后错得非常隐蔽：题目保证入口是空格，入口又完全可能落在边界上（官方样例 2 的 entrance = [1, 0] 就在第 0 列，样例 3 的 entrance = [0, 0] 更是在角上），如果把「在边界上的空格」直接当成出口，那么这两个样例都会在原地就宣布找到出口，答案变成 0。落实这条约束的干净做法是：只在扩展到的新格子上做出口判定，绝不对当前正在处理的格子判定。入口是唯一一个不经扩展就进入搜索的格子，因此只要判定动作发生在「跨出一步之后」，入口天然被排除。另一种等价写法是保留对当前格的判定，但额外加上 !(row == entrance[0] && col == entrance[1])；不过多一个条件就多一个出错点，前者更值得记。

约束里 1 <= m, n <= 100，格子总数最多 10000，规模非常小，$O(mn)$ 的做法绰绰有余，反过来也说明出题人期待的就是一次线性遍历级别的解法。

边界情况有三类需要单独想清楚：其一是 1 x 1 或 1 x n 这类退化矩阵，此时所有格子都在边界上，入口的四个邻居要么越界要么是墙，答案只能是 -1（样例 3 就是 1 x 2 的 [[".", "+"]]，返回 -1）；其二是入口在边界上但四周被墙封死，同样返回 -1，绝不能因为入口在边界就返回 0；其三是入口在内部且有多个出口，必须取最近的那个，而不是最先在代码里被遍历到的那个。

顺带一提，题目只要求返回步数，不要求还原具体路径，所以不需要记录前驱格子。

解法：BFS 逐层扩展求最短步数

核心思路

把每个空格看作图的一个结点，相邻且都是空格的两格之间连一条长度为 1 的边，问题就是求入口到「任意一个边界空格（入口除外）」的最短距离。等权图上的最短路用 BFS：用一个队列维护当前这一层的格子，每轮把整层一次性取出并向四周扩展，扩展出的新格子构成下一层。

正确性来自 BFS 的核心性质：按层扩展保证第一次到达某个格子时的步数就是它到入口的最短步数。可以把它写成一个循环不变量来看清楚——每轮 while 循环开始时，队列里恰好装着所有距入口相同步数的、已被发现且尚未扩展过的空格，每格只出现一次。设这个步数是 d：本轮先记下 size = queue.size()，只处理这 size 个格子，它们的四邻中所有还没被标记过的空格距入口恰好是 d + 1 步（不可能更少，否则它会在更早的某一层就被发现并标记掉），这些新格子入队后，本轮结束时队列里正好是距入口 d + 1 步的全部格子，不变量得以保持。初始时队列只有入口一格、d = 0，不变量成立。于是当某一轮扩展中第一次撞到一个边界空格时，当前的 steps 就是最短步数，可以立刻返回；队列耗尽说明入口所在的连通块里根本没有边界空格，返回 -1。

这里必须用「先取 size、再循环 size 次」的写法把层与层切开，而不能在循环体内直接对 steps 累加。因为一次 poll 只是取出一个格子，并不代表走了一步；只有整层处理完，距离才真正加一。如果不分层，就只能改成在队列元素里额外存一个 dist 字段，两种写法都对，但按层计数少存一个字段，白板上更短。

另一个必须想清楚的点是「入队即标记已访问」，也就是在 queue.offer 的同时把格子标成已访问，而不是等它出队时才标记。如果推迟到出队才标记，同一个格子会被它的多个邻居各自入队一次，队列里出现重复元素：本题的网格每格最多 4 个邻居，重复量是常数倍（实测 100 x 100 的图上出队次数从 9604 涨到 19013，峰值队列长度从 194 涨到 386），虽然靠出队时的二次判重仍能得到正确答案，但「每格最多入队一次」这个支撑复杂度分析的前提没了；换到出度更大的状态图上（比如打开转盘锁那类题），放大倍数就是出度本身，队列会明显膨胀。所以入队即标记应当作为肌肉记忆写进模板。

标记的具体方式，本题可以省掉 visited 数组：直接把访问过的格子原地改成 '+'。墙和已访问格子在后续判断里的作用完全一样（都不能再走），所以一个 if (maze[r][c] == '+') continue; 就同时挡住了这两种情况，代码短且不用额外空间。代价是破坏了输入矩阵——如果调用方之后还要复用 maze，或者需要在同一个矩阵上跑多次查询，这种写法就不合适，应该换成独立的 boolean[][] visited（额外 $O(mn)$ 空间，逻辑完全一致）。面试时最好主动说一句「我原地标记以省空间，如果不允许修改输入我改用 visited 数组」，这是加分项而不是偷懒。

入口自己也要在初始化时一并标记掉：它既防止搜索绕回起点重复入队，也顺手把「入口被当成出口」的可能性彻底掐死——被标成 '+' 之后，任何一次扩展都不会再看上它。

解题步骤

取出 m = maze.length、n = maze[0].length。列数必须用 maze[0].length，因为本题是 m x n 的一般矩形而不是方阵，用 maze.length 当列数会在长条形迷宫上判错边界。

准备方向数组 {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}，对应上、下、左、右四个方向。只有四方向，写成对角线的八方向会凭空多出穿越墙角的走法，把答案算小。

建立队列并把入口入队，同时把 maze[entrance[0]][entrance[1]] 改成 '+'。为什么：入口即第 0 层；标记它既避免回头重复入队，也保证入口永远不会被判成出口。

初始化 steps = 0，表示队列里当前这层距入口 0 步。

进入 while (!queue.isEmpty()) 循环，每轮一开始先 steps++，再取 size = queue.size()。为什么：本轮扩展出来的所有新格子距入口都是 steps 步，先自增可以让返回值直接就是 steps，不必再写 steps + 1；先取 size 是为了固定本层的边界，循环体内 queue 会因入队而变长，size 必须在扩展之前快照。

内层循环 size 次，每次 poll 一个格子并枚举四个方向，得到 (nextRow, nextCol)。

先判越界 nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n，再判 maze[nextRow][nextCol] == '+'，两者任一成立就 continue。为什么这个顺序：不先排除越界就直接下标访问会抛数组越界异常；而 '+' 这一个条件同时挡住了墙和已访问格子。

接着判断新格子是否在边界上：nextRow == 0 || nextRow == m - 1 || nextCol == 0 || nextCol == n - 1，成立就直接 return steps。为什么：判定只发生在「跨出一步之后到达的新格子」上，所以入口不可能被判成出口；又因为是按层推进，第一次撞上的边界空格必然是最近的出口。

否则把新格子标成 '+' 并入队。为什么先标记再入队（顺序上写在一起即可）：入队即标记，同一格只会进队列一次。

循环正常结束（队列耗尽）时 return -1，表示入口所在连通块内没有可达出口。

以 maze = [["+","+","+"],[".",".","."],["+","+","+"]]、entrance = [1, 0] 走一遍：m = 3、n = 3。初始化后把 (1,0) 改成 '+'，队列 [(1,0)]，steps = 0。第一轮：steps 变为 1，size = 1，取出 (1,0)，四个方向依次是 (0,0) 是墙跳过、(2,0) 是墙跳过、(1,-1) 越界跳过、(1,1) 是空格且行 1 不等于 0 或 2、列 1 也不等于 0 或 2，不在边界上，于是标记并入队；本轮结束队列为 [(1,1)]，正好是距入口 1 步的全部格子。第二轮：steps 变为 2，size = 1，取出 (1,1)，(0,1) 是墙、(2,1) 是墙、(1,0) 已被标成 '+' 跳过、(1,2) 是空格且列 2 == n - 1 落在边界上，return 2。与期望输出一致；注意入口 (1,0) 本身也在第 0 列上，但它从未被拿去做出口判定，所以不会错误地返回 0。

再看 -1 的用例 maze = [[".","+"]]、entrance = [0, 0]：m = 1、n = 2。初始化后 (0,0) 改成 '+'，队列 [(0,0)]。第一轮 steps 变为 1，取出 (0,0)，(-1,0) 与 (1,0) 越界、(0,-1) 越界、(0,1) 是墙，四个方向全部被挡住，没有任何新格子入队。本轮结束后队列为空，while 退出，返回 -1。整个过程中入口虽然既在第 0 行又在第 0 列，也没有被误判为出口。

代码实现

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        // 上、下、左、右四个方向
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{entrance[0], entrance[1]});
        // 入口原地标记为墙：既防止回头，也保证入口不会被判成出口
        maze[entrance[0]][entrance[1]] = '+';
        int steps = 0;
        while (!queue.isEmpty()) {
            // 本轮扩展出的新格子距入口都是 steps 步
            steps++;
            // 先快照本层大小，循环体内队列会变长
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] d : dirs) {
                    int nextRow = cur[0] + d[0];
                    int nextCol = cur[1] + d[1];
                    if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) {
                        continue;
                    }
                    // '+' 同时代表墙和已访问过的格子
                    if (maze[nextRow][nextCol] == '+') {
                        continue;
                    }
                    // 只对「跨出一步后到达的新格子」判出口，入口天然被排除
                    if (nextRow == 0 || nextRow == m - 1 || nextCol == 0 || nextCol == n - 1) {
                        return steps;
                    }
                    // 入队即标记，保证每格最多入队一次
                    maze[nextRow][nextCol] = '+';
                    queue.offer(new int[]{nextRow, nextCol});
                }
            }
        }
        return -1;
    }
}

func nearestExit(maze [][]byte, entrance []int) int {
    m, n := len(maze), len(maze[0])
    // 上、下、左、右四个方向
    dirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    queue := [][2]int{{entrance[0], entrance[1]}}
    // 入口原地标记为墙：既防止回头，也保证入口不会被判成出口
    maze[entrance[0]][entrance[1]] = '+'
    steps := 0
    for len(queue) > 0 {
        // 本轮扩展出的新格子距入口都是 steps 步
        steps++
        // 先快照本层大小，循环体内队列会变长
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            for _, d := range dirs {
                nextRow, nextCol := cur[0]+d[0], cur[1]+d[1]
                if nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n {
                    continue
                }
                // '+' 同时代表墙和已访问过的格子
                if maze[nextRow][nextCol] == '+' {
                    continue
                }
                // 只对「跨出一步后到达的新格子」判出口，入口天然被排除
                if nextRow == 0 || nextRow == m-1 || nextCol == 0 || nextCol == n-1 {
                    return steps
                }
                // 入队即标记，保证每格最多入队一次
                maze[nextRow][nextCol] = '+'
                queue = append(queue, [2]int{nextRow, nextCol})
            }
        }
    }
    return -1
}

复杂度分析

时间复杂度：$O(mn)$，因为入队即标记，每个空格最多入队一次、出队一次，出队后只做常数次（四个方向）的检查。

空间复杂度：$O(mn)$，队列最坏时同层格子数量为 $O(mn)$；原地把走过的格子改成 '+' 后不需要额外的访问标记数组。

关键点总结

听到「最少步数」且「每步代价相同」就该立刻锁定逐层扩展的 BFS：一圈一圈往外推，圈号即距离，第一次命中目标就是最优解。代价不等（比如每步花费不同、或像 505 那样一路滚到底才算一步）时这个等价关系就断了，得换 Dijkstra 或改造状态。

入队即标记是 BFS 模板里不可动摇的一条。它把「每格最多入队一次」变成不变式，既是 $O(mn)$ 复杂度的依据，也避免队列里堆满重复元素。

按层计数（每轮先取队列长度）与在结点里存 dist是两种等价的距离记法，选前者能少存一个字段；关键是别把「出队一个元素」误当成「走了一步」。

需要「已访问」标记时，先看能不能复用输入的取值空间（本题把走过的格子改成 '+'），省下一个数组；但要清楚这破坏了输入，不允许修改时改用 visited 数组。

题面里对目标的排除性定义（「不是入口本身」）要落到代码结构上而不是靠额外的 if 打补丁：把判定点放在「跨出一步之后」，起点就自动不满足条件。

面试视角：这题面试官期待的是听到「最少步数 + 等权移动」后直接给出 BFS，不要在最短路问题上写 DFS 回溯（DFS 需要穷举所有路径才能确认最短，指数级且不是期望答案）。写完之后高频追问有两个——「入队即标记和出队才标记有什么区别」（考队列重复元素与复杂度不变式），以及「为什么第一次到达就是最短」（考按层扩展的循环不变量）。另外常被追问「原地改 maze 有什么副作用」，答「破坏输入，可改用 visited 数组」即可。

易错点总结

在出队时判定当前格是否在边界（把「在边界上的空格」直接当出口）：触发用例 maze = [["+","+","+"],[".",".","."],["+","+","+"]]、entrance = [1, 0] → 入口本身在第 0 列，第一次出队就返回 0，正确答案是 2；样例 3 [[".","+"]]、entrance = [0, 0] 同样返回 0，正确答案是 -1；入口在边界且要绕远的用例 [["+",".","+","+","+"],["+",".",".",".","+"],["+",".",".",".","+"],["+","+","+",".","+"]]、entrance = [0, 1] 返回 0，正确答案是 5。

忘记在初始化时标记入口（只在扩展时标记）：触发用例上面那个绕远迷宫 entrance = [0, 1] → 走到 (1,1) 后再回头看 (0,1)，发现它是未标记的边界空格，返回 2，正确答案是 5。

出队时才标记已访问：触发用例 100 x 100、最外圈全是墙、内部全空、entrance = [50, 50]（答案 -1） → 答案虽然仍对，但出队次数从 9604 涨到 19013，峰值队列长度从 194 涨到 386，「每格最多入队一次」的复杂度依据失效；换成出度更大的状态图时膨胀倍数等于出度。

把 steps++ 放在本层处理完之后（steps 从 0 起且层末自增）：触发用例样例 1 [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]]、entrance = [1, 2] → 返回 0，正确答案是 1；样例 2 返回 1，正确答案是 2；绕远用例返回 4，正确答案是 5。整体少一步。

不按层计数，每出队一个元素就 steps++：触发用例 [["+",".","+","+","+"],["+",".",".",".","+"],["+",".","+",".","+"],["+",".",".",".","+"],["+","+","+",".","+"]]、entrance = [2, 3] → 返回 3，正确答案是 2；上面的绕远用例返回 7，正确答案是 5。steps 变成了「出队计数」而不是「层数」。

边界判定只写了行、漏了列（只判 nextRow == 0 || nextRow == m - 1）：触发用例样例 2 entrance = [1, 0] → 唯一出口 (1,2) 在最后一列，永远不会被识别，返回 -1，正确答案是 2。

列数误用 maze.length（默认输入是方阵）：触发用例 [["+","+","+","+","+"],["+",".",".",".","."],["+","+","+","+","+"]]、entrance = [1, 1] → n 被当成 3，(1,2) 被错判成最后一列上的出口，返回 1，正确答案是 3。

方向数组抄成八方向：触发用例绕远迷宫 entrance = [0, 1] → 允许斜穿墙角，返回 3，正确答案是 5。

原地把走过的格子改成 '+' 却忽略了输入被破坏：触发用例是拿同一份 maze 数组连续调用两次（本地写测试时最容易踩），样例 2 [["+","+","+"],[".",".","."],["+","+","+"]]、entrance = [1, 0] → 第一次返回 2，第二次和第三次都返回 -1，因为中间那条通路已经被标记成 '+'；绕远用例 entrance = [0, 1] 同样从 5 变成 -1。写测试或需要复用输入时必须先深拷贝，或改用独立的 visited 数组。

相似题目

题目	难度	考察点
1091. 二进制矩阵中的最短路径	中等	同为网格等权最短路，但可走八方向、终点是固定的右下角，无需处理「起点不算终点」
542. 01 矩阵	中等	目标反过来：求每个格子到最近 `0` 的距离，需把所有 `0` 一次性入队做多源 BFS
994. 腐烂的橘子	中等	同样按层计数，但起点是多个腐烂橘子，且要求「扩展到所有目标」的层数而非首次命中
505. 迷宫 II	中等	移动规则变成一路滚到墙才停，每步代价不再是 `1`，逐层扩展失效，需要 Dijkstra 或松弛
200. 岛屿数量	中等	只要连通性不要距离，无需分层，可换成 DFS 或并查集，标记手法与本题原地改字符一致
130. 被围绕的区域	中等	同样围绕「边界」做文章，但方向相反：从所有边界空格反向搜索标记不被围绕的区域