迷宫中离入口最近的出口

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze

问题叙述

给你一个 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 一定是空格子。

分析

经典的BFS模板题，用BFS能保证找到的出口是最近的。相当于一层一层扩展，第一次将距离入口为1的格子加入到队列中，第二次将距离入口为2的格子加入到队列中，同时每次将已经遍历过的格子设成墙，这样一定能保证我们遍历到的出口是最近的。

创建一个Point类用来记录坐标，同时创建两个一维数组，用来遍历四个方向。

之后的代码就与二叉树的层序遍历模板差不多了，每次从队列中取出一个坐标，判断该坐标上下左右四个方向是否能走，如果能走的话，判断一下是不是到了出口（边界就是出口），如果是出口，就直接返回当前的step，如果不是的话，就把坐标加入到队列中，同时将该坐标设为墙。

如果没有找到出口的话，最终返回-1即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int[] X = new int[]{-1, 0, 0, 1};
    int[] Y = new int[]{0, 1, -1, 0};
    LinkedList<Point> deque = new LinkedList<>();
    int step = 0;

    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        deque.add(new Point(entrance[0], entrance[1]));
        maze[entrance[0]][entrance[1]] = '+';
        while (!deque.isEmpty()) {
            int size = deque.size();
            step++;
            for (int i = 0; i < size; i++) {
                Point p = deque.pollFirst();
                for (int j = 0; j < 4; j++) {
                    int x = p.x + X[j];
                    int y = p.y + Y[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') {
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        deque.add(new Point(x, y));
                        maze[x][y] = '+';
                    }
                }
            }
        }
        return -1;
    }
}