迷宫中离入口最近的出口
难度:
标签:
题目描述
给你一个 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
一定是空格子。
代码结果
运行时间: 68 ms, 内存: 17.7 MB
/**
* Similar to the Java solution but using Java Streams to process the queue operations and directions.
* Streams allow us to work with data in a declarative way, making the code more readable.
* The logic remains the same as we perform BFS to find the nearest exit.
*/
import java.util.*;
import java.util.stream.*;
public class SolutionStream {
public int nearestExit(char[][] maze, int[] entrance) {
int rows = maze.length;
int cols = maze[0].length;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{entrance[0], entrance[1]});
maze[entrance[0]][entrance[1]] = '+';
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
steps++;
queue = IntStream.range(0, size)
.mapToObj(i -> queue.poll())
.flatMap(point -> Arrays.stream(directions)
.map(dir -> new int[]{point[0] + dir[0], point[1] + dir[1]})
.filter(newPoint -> newPoint[0] >= 0 && newPoint[1] >= 0 && newPoint[0] < rows && newPoint[1] < cols && maze[newPoint[0]][newPoint[1]] == '.')
.peek(newPoint -> maze[newPoint[0]][newPoint[1]] = '+')
.peek(newPoint -> {
if (newPoint[0] == 0 || newPoint[1] == 0 || newPoint[0] == rows - 1 || newPoint[1] == cols - 1) throw new RuntimeException(String.valueOf(steps));
})
).collect(Collectors.toCollection(LinkedList::new));
}
return -1;
}
}
解释
方法:
本题解采用广度优先搜索(BFS)算法,从入口开始探索迷宫,直到找到边界上的一个空格子作为出口。首先,将入口标记为已访问(用'+'替代'.'),以避免重复访问。然后,从入口开始,对周围的格子进行检查,如果是空格子并且位于边界,则直接返回结果;否则,将该格子标记为已访问,并将其加入队列中。接下来,对队列中的格子依次执行上述操作,直到队列为空或找到出口。如果无法到达任何出口,返回-1。
时间复杂度:
O(m*n)
空间复杂度:
O(m*n)
代码细节讲解
🦆
在题解中,为什么在BFS的每一层遍历完后要清空当前层的列表并更新为新层?这种处理方式有什么特别的优点吗?
▷🦆
题解中提到,如果当前格子已经是边界格子就可以直接返回步数。请问这种情况是如何处理的,具体是在哪一部分代码中实现的?
▷🦆
题解提到使用'+'标记已访问的格子,以避免重复访问。这种标记方法对算法的效率和结果正确性有何影响?
▷🦆
题解中初始化步数为1,这种初始化方式是基于什么考虑?在哪些情况下这种初始化可能导致问题?
▷