原文链接: https://leetcode-cn.com/problems/nearest-exit-from-entrance-in-maze

英文原文

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

 

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

 

Constraints:

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] is either '.' or '+'.
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance will always be an empty cell.

中文题目

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

通过代码

高赞题解

• 创建Point类，属性为横坐标、纵坐标、步数。
• 使用Queue来依次将Point入队、出队。
• 由于是广度优先搜索，所以最先出队并且满足要求的路径就是最短的路径。

class Solution {
    class Point {
        /**
         * 横坐标
         */
        int x;
        /**
         * 纵坐标
         */
        int y;
        /**
         * 步数
         */
        int step;

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

    public int nearestExit(char[][] maze, int[] entrance) {
        return bfs(maze, entrance[0], entrance[1]);
    }

    public int bfs(char[][] maze, int i, int j) {
        //可以移动的方向
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int m = maze.length;
        int n = maze[0].length;
        Queue<Point> queue = new LinkedList<>();
        //入口入队
        queue.offer(new Point(i, j, 0));
        //标记为已访问过
        maze[i][j] = '+';
        while (!queue.isEmpty()) {
            Point poll = queue.poll();
            //不是入口，且是边界
            if (!(poll.x == i && poll.y == j) && (poll.x == 0 || poll.x == m - 1 || poll.y == 0 || poll.y == n - 1)) {
                return poll.step;
            }
            //枚举四个方向
            for (int k = 0; k < dx.length; k++) {
                int x = poll.x + dx[k];
                int y = poll.y + dy[k];
                //没越界且未访问过
                if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') {
                    queue.offer(new Point(x, y, poll.step + 1));
                    //标记为已访问过
                    maze[x][y] = '+';
                }
            }
        }
        //程序运行到这里，说明不存在这样的路径，返回 -1
        return -1;
    }
}

统计信息

通过次数	提交次数	AC比率
3906	11319	34.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言