LeetCode——1926. 迷宫中离入口最近的出口(Nearest Exit from Entrance in Maze)[中等]——分析及代码（Java）

一、题目

给你一个 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 == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] 要么是 ‘.’ ，要么是 ‘+’ 。
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance 一定是空格子。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nearest-exit-from-entrance-in-maze
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析及代码

1. 广度优先搜索

（1）思路

结合广度优先搜索方法，从入口开始依次在迷宫中遍历所有可到达的位置，判断出口是否存在并求解最少步数。

（2）代码

class Solution {
    int m, n;//矩阵行数、列数
    int multi = 1000;//通过 x * multi + y 将二维坐标转化为单个数字
    int[] detX = new int[]{-1, 1, 0, 0};//左、右、上、下的横坐标变化
    int[] detY = new int[]{0, 0, -1, 1};//左、右、上、下的纵坐标变化
    Set<Integer> set = new HashSet<Integer>();//已到达过的位置//也可直接将到达过的空格子变为墙格子，简化实现过程
    Queue<Integer> que = new LinkedList<Integer>();//待探索的位置队列

    public int nearestExit(char[][] maze, int[] entrance) {
        this.m = maze.length;
        this.n = maze[0].length;

        //将入口位置压缩为单个数字并入队
        int ent = entrance[0] * multi + entrance[1];
        set.add(ent);
        que.offer(ent);
        int step = 1;//初始化步数为1

        //广度优先搜索
        while (!que.isEmpty()) {
            int size = que.size();//当前步数对应的位置
            for (int i = 0; i < size; i++) {//遍历所有当前步数对应的位置
                int point0 = que.poll();//提取位置
                int x0 = point0 / multi, y0 = point0 % multi;//计算位置的坐标
                for (int j = 0; j < 4; j++) {//遍历左、右、上、下四个位置
                    int x = x0 + detX[j], y = y0 + detY[j];
                    int point = x * multi + y;
                    if (validPoint(x, y) && maze[x][y] == '.' && !set.contains(point)) {//位置有效、为空格子且未到达过
                        if (isExit(x, y))//判断是否为出口
                            return step;
                        set.add(point);//记录已到达过该位置
                        que.offer(point);//入队
                    }
                }
            }
            step++;//当前批次位置探索完成，步数+1
        }
        return -1;//所有可到达的位置已遍历过，说明无有效出口
    }

    //判断位置是否有效
    public boolean validPoint(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    //判断位置是否为出口
    public boolean isExit(int x, int y) {
        return x == 0 || x == m - 1 || y == 0 || y == n - 1;
    }
}

（3）结果

执行用时 ：16 ms，在所有 Java 提交中击败了 16.46% 的用户；
内存消耗 ：39.7 MB，在所有 Java 提交中击败了 39.00% 的用户。

三、其他

也可直接将到达过的空格子变为墙格子，简化实现过程。