LeetCode_BFS_中等_1926.迷宫中离入口最近的出口

╰+攻爆jí腚メ 2023-10-16 14:42 16阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = \[entrancerow, entrancecol\] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的空格子。entrance 格子不算出口。

请你返回从 entrance 到最近出口的最短路径的步数 ，如果不存在这样的路径，请你返回 -1。

**示例 1：**

![在这里插入图片描述][b03d141d59a546c9b716d328555dc3f8.png]

输入：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：**

![在这里插入图片描述][ec52d5fe24a34481ab87f52e43915f55.png]

输入：maze = \[\[“+”,“+”,“+”\],\[“.”,“.”,“.”\],\[“+”,“+”,“+”\]\], entrance = \[1,0\]  
输出：2  
解释：迷宫中只有 1 个出口，在 (1,2) 处。  
(1,0) 不算出口，因为它是入口格子。  
初始时，你在入口与格子 (1,0) 处。

*  你可以往右移动 2 步到达 (1,2) 处。  
    所以，最近的出口为 (1,2) ，距离为 2 步。

**示例 3：**  
![在这里插入图片描述][451a37d9327e45d28524bc64cf1df35b.png]

输入：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 一定是空格子。

## 2.思路 ##

（1）BFS

## 3.代码实现（Java） ##

//思路1————BFS
    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 LinkedList<>();
            queue.offer(new int[]{
        entrance[0], entrance[1], 0});
            maze[entrance[0]][entrance[1]] = '+';
            while (!queue.isEmpty()) {
        
                int[] curPos = queue.poll();
                int curX = curPos[0];
                int curY = curPos[1];
                int dis = curPos[2];
                //朝上下左右四个方向进行遍历
                for (int[] dir : dirs) {
        
                    int nx = curX + dir[0];
                    int ny = curY + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.') {
        
                        if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {
        
                            return dis + 1;
                        }
                        maze[nx][ny] = '+';
                        queue.offer(new int[]{
        nx, ny, dis + 1});
                    }
                }
            }
            return -1;
        }
    }

[b03d141d59a546c9b716d328555dc3f8.png]: https://img-blog.csdnimg.cn/b03d141d59a546c9b716d328555dc3f8.png
[ec52d5fe24a34481ab87f52e43915f55.png]: https://img-blog.csdnimg.cn/ec52d5fe24a34481ab87f52e43915f55.png
[451a37d9327e45d28524bc64cf1df35b.png]: https://img-blog.csdnimg.cn/451a37d9327e45d28524bc64cf1df35b.png