• 欢迎光临~

[LeetCode] 1926. 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.

Java实现

``` 1 class Solution {
2     public int nearestExit(char[][] maze, int[] entrance) {
3         int m = maze.length;
4         int n = maze[0].length;
5         Queue<int[]> queue = new LinkedList<>();
6         queue.offer(entrance);
7         maze[entrance[0]][entrance[1]] = '+';
8
9         int steps = 0;
10         int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
11         while (!queue.isEmpty()) {
12             steps++;
13             int size = queue.size();
14             for (int i = 0; i < size; i++) {
15                 int[] cur = queue.poll();
16                 for (int[] dir : dirs) {
17                     int newX = cur[0] + dir[0];
18                     int newY = cur[1] + dir[1];
19                     if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;
20                     if (maze[newX][newY] == '+') continue;
21
22                     // return
23                     if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1) {
24                         return steps;
25                     }
26                     maze[newX][newY] = '+';
27                     queue.offer(new int[] {newX, newY});
28                 }
29             }
30         }
31         return -1;
32     }
33 }```

LeetCode 题目总结