1926. 迷宫中离入口最近的出口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 一定是空格子。

# 思路

bfs

# 解法

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(entrance);
        visited[entrance[0]][entrance[1]] = true;

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int step = 0;
        while(!q.isEmpty()){
            int sz = q.size();

            for(int i = 0; i < sz; i++){
                int[] cur = q.poll();

                if(cur[0] == 0 || cur[0] == m - 1 || cur[1] == 0 || cur[1] == n - 1){
                    if(cur[0] != entrance[0] || cur[1] != entrance[1]){
                        return step;
                    }
                }

                for(int[] dir : dirs){
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];

                    if(x < 0 || x >= m || y < 0 || y >= n || maze[x][y] == '+'){
                        continue;
                    }

                    if(visited[x][y]){
                        continue;
                    }

                    q.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
            step++;
        }

        return -1;
    }
}

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
41
42
43
44
45
46

# 总结

分析出几种情况，然后分别对各个情况实现

#Java