leetcode
leetcode 1701 ~ 1750
迷宫中离入口最近的出口

迷宫中离入口最近的出口

难度:

标签:

题目描述

给你一个 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的每一层遍历完后要清空当前层的列表并更新为新层?这种处理方式有什么特别的优点吗?
在BFS中清空当前层的列表并更新为新层是为了保持层次遍历的清晰结构。这种处理方式确保了每一次循环中只处理当前层的节点,并且在处理完所有当前层的节点后,再集中处理下一层的节点。这样做的优点包括:1) 结构清晰易于理解,每层的处理被清晰隔离;2) 便于计算从起点到当前节点的距离,因为每完成一层的处理,步数就统一增加1,这对于寻找最短路径问题特别有用。
🦆
题解中提到,如果当前格子已经是边界格子就可以直接返回步数。请问这种情况是如何处理的,具体是在哪一部分代码中实现的?
在题解代码中,每次在处理节点时,首先会检查节点是否位于边界上(即是否在迷宫的四周)。这是在代码的各个分支中实现的:例如,在向上移动时,如果`x`为0,表示当前格子已在最上边界,此时会直接返回`res`,即当前的步数。类似的检查也发生在向左、向右和向下移动时,如果`y`为0或`y`为`n-1`,或者`x`为`m-1`,分别表示当前格子已在左、右或下边界。
🦆
题解提到使用'+'标记已访问的格子,以避免重复访问。这种标记方法对算法的效率和结果正确性有何影响?
使用'+'标记已访问的格子可以有效地避免在BFS过程中重复访问同一个格子,这对于防止无限循环和减少不必要的计算非常关键。此外,这种方法也有助于确保算法的结果正确性,因为它确保每个格子只被计算一次,从而保证找到的是最短路径。在效率方面,这种标记方法直接修改了迷宫数组,避免了额外的空间开销,如使用独立的访问数组等,因此在空间利用上更为高效。
🦆
题解中初始化步数为1,这种初始化方式是基于什么考虑?在哪些情况下这种初始化可能导致问题?
在题解中,初始化步数为1是因为算法从入口开始做第一次移动即计算为一步。这是基于入口自身不计入步数,只有从入口开始移动时才开始计数的考虑。这种初始化方式通常适用于需要计算从一个点到另一个点的最小步数的场景。然而,这种初始化可能导致问题如果算法或问题的描述中入口处本身就被认为是第一步或需要计入步数时,此时初始化应为0。此外,如果迷宫中入口即出口的情况没有被特殊处理,这种初始化也可能导致错误的步数计算。

相关问题