---
comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/solution/1900-1999/1926.Nearest%20Exit%20from%20Entrance%20in%20Maze/README.md
rating: 1638
source: 第 56 场双周赛 Q2
tags:
- 广度优先搜索
- 数组
- 矩阵
---
# [1926. 迷宫中离入口最近的出口](https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze)
[English Version](/solution/1900-1999/1926.Nearest%20Exit%20from%20Entrance%20in%20Maze/README_EN.md)
## 题目描述
给你一个 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 == mmaze[i].length == n1 <= m, n <= 100maze[i][j] 要么是 '.' ，要么是 '+' 。entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrance 一定是空格子。
## 解法
### 方法一
#### Python3
```python
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
```
#### Java
```java
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int m = maze.length;
int n = maze[0].length;
Deque 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;
}
}
```
#### C++
```cpp
class Solution {
public:
int nearestExit(vector>& maze, vector& entrance) {
int m = maze.size(), n = maze[0].size();
queue> q{{entrance}};
maze[entrance[0]][entrance[1]] = '+';
int ans = 0;
vector 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;
}
};
```
#### Go
```go
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
}
```
#### TypeScript
```ts
function nearestExit(maze: string[][], entrance: number[]): number {
const m = maze.length;
const n = maze[0].length;
const dir = [0, 1, 0, -1, 0];
const q = [[...entrance, 0]];
maze[entrance[0]][entrance[1]] = '+';
for (const [i, j, ans] of q) {
for (let d = 0; d < 4; d++) {
const [x, y] = [i + dir[d], j + dir[d + 1]];
const v = maze[x]?.[y];
if (!v && ans) {
return ans;
}
if (v === '.') {
q.push([x, y, ans + 1]);
maze[x][y] = '+';
}
}
}
return -1;
}
```