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

2026-07-14 HGNULB 约 7 分钟

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

分类

LeetCode 中等 LeetCode 75

标签

数组 广度优先搜索 矩阵

题目描述

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

题意分析

从迷宫入口出发，每次只能向上、下、左、右移动一格，不能穿墙或走出矩阵。出口是矩阵边界上的空格，求到达任意出口所需的最少步数，无法到达则返回 -1。

入口即使位于边界，也不能算出口；必须到达另一个边界空格。走到边界格就已经完成，不需要再跨出迷宫一步。距离统计的是移动次数，不是路径中的格子数量。

解法：从入口 BFS 找第一个新到达的边界空格

核心思路

[!blue]

每次移动代价都是一步，适合从入口做 BFS。距离为零的入口先入队，然后逐层扩展距离为一、二的格子。先处理完较近的位置，才处理更远的位置，所以第一次发现新边界空格时，得到的就是最近出口。

每轮开始先将 steps 加一，再固定当前队列大小 size。此时队列中的节点距离为 steps - 1，它们新发现的邻居距离为 steps。只处理固定的 size 个节点，过程中加入的邻居留到下一轮，避免把不同距离混在一起。

入队之前把空格改成墙标记 +，让墙和已访问格子统一被跳过。一个格子第一次被找到时距离已经最短，之后通过其他路径再访问它不会改进答案，因此无需重复入队。入口最初就被标记，既防止走回入口，也保证它不会被当作新出口。

对邻居先检查范围和是否为未访问空格，再判断是否位于边界；命中即可返回，不必把出口继续加入队列。队列耗尽仍未找到，说明入口可达的所有空格都检查完了。当前实现使用原迷宫保存访问标记，会修改输入。

解题步骤

1. 将入口加入队列，并将入口格标记为 +，步数初始为零。
2. 每轮增加步数、固定当前层队列大小，只扩展这一层节点。
3. 对四个相邻位置依次排除越界、墙和已经访问的格子。
4. 新空格位于边界时立即返回当前步数；否则先标记再入队。
5. 全部可达位置处理完仍无出口，返回 -1。

代码实现

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)$，队列最坏保存线性数量的网格位置。访问标记复用输入矩阵，没有额外访问数组。

关键点总结

[!green]

• 单位移动代价保证 BFS 按最短距离逐层到达。
• 当前层出队节点比新邻居少一步，steps 对应的是新到达位置的距离。
• 入口预先标记，只对新邻居判出口，自然排除零步返回入口。
• 入队即标记，避免同一层的不同路径重复安排同一个格子。

易错点总结

[!yellow]

• 入口位于边界就返回零，违反入口不算出口的规定。
• 到达边界后再多加一步，求成离开矩阵的距离。
• 内层使用不断增长的队列大小，将下一层也在本轮处理，步数不再准确。
• 出队时才标记，同一个空格可能被多个邻居重复加入。
• 在检查坐标有效之前访问矩阵，或允许对角线移动，会越界或改变题目的路径规则。

相似题目

题目	难度	关联与区别
1091. 二进制矩阵中的最短路径	中等	同样在网格中用BFS求最短路，原题允许八方向且有固定终点，本题四方向并寻找任意边界出口。
994. 腐烂的橘子	中等	同样按层传播，原题从多个腐烂源同时开始，本题只有一个入口。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/19778392

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！