Description#
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:
![](https://spcdn.pages.dev/leetcode/problems/1926.Nearest%20Exit%20from%20Entrance%20in%20Maze/images/nearest1-grid.jpg)
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:
![](https://spcdn.pages.dev/leetcode/problems/1926.Nearest%20Exit%20from%20Entrance%20in%20Maze/images/nearesr2-grid.jpg)
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:
![](https://spcdn.pages.dev/leetcode/problems/1926.Nearest%20Exit%20from%20Entrance%20in%20Maze/images/nearest3-grid.jpg)
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.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
m, n = len(maze), len(maze[0])
i, j = entrance
q = deque([(i, j)])
maze[i][j] = '+'
ans = 0
while q:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and maze[x][y] == '.':
if x == 0 or x == m - 1 or y == 0 or y == n - 1:
return ans
q.append((x, y))
maze[x][y] = '+'
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
| class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int m = maze.length;
int n = maze[0].length;
Deque<int[]> q = new ArrayDeque<>();
q.offer(entrance);
maze[entrance[0]][entrance[1]] = '+';
int ans = 0;
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
++ans;
for (int k = q.size(); k > 0; --k) {
int[] p = q.poll();
int i = p[0], j = p[1];
for (int l = 0; l < 4; ++l) {
int x = i + dirs[l], y = j + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') {
if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {
return ans;
}
q.offer(new int[] {x, y});
maze[x][y] = '+';
}
}
}
}
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
| class Solution {
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size(), n = maze[0].size();
queue<vector<int>> q{{entrance}};
maze[entrance[0]][entrance[1]] = '+';
int ans = 0;
vector<int> dirs = {-1, 0, 1, 0, -1};
while (!q.empty()) {
++ans;
for (int k = q.size(); k > 0; --k) {
auto p = q.front();
q.pop();
for (int l = 0; l < 4; ++l) {
int x = p[0] + dirs[l], y = p[1] + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') {
if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return ans;
q.push({x, y});
maze[x][y] = '+';
}
}
}
}
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
| func nearestExit(maze [][]byte, entrance []int) int {
m, n := len(maze), len(maze[0])
q := [][]int{entrance}
maze[entrance[0]][entrance[1]] = '+'
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
ans++
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
for l := 0; l < 4; l++ {
x, y := p[0]+dirs[l], p[1]+dirs[l+1]
if x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' {
if x == 0 || x == m-1 || y == 0 || y == n-1 {
return ans
}
q = append(q, []int{x, y})
maze[x][y] = '+'
}
}
}
}
return -1
}
|