迷宫中离入口最近的出口

标签: 广度优先搜索 数组 矩阵

难度: Medium

给你一个 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 一定是空格子。

Submission

运行时间: 68 ms

内存: 17.7 MB

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m = len(maze)
        n = len(maze[0])
        res = 1
        x, y = entrance
        prev = []
        new = []

        maze[x][y] = "+"
        if x:
            x -= 1
            if maze[x][y] == ".":
                maze[x][y] = "+"
                prev.append((x, y))
            x += 1
        if x < m - 1:
            x += 1
            if maze[x][y] == ".":
                maze[x][y] = "+"
                prev.append((x, y))
            x -= 1
        if y:
            y -= 1
            if maze[x][y] == ".":
                maze[x][y] = "+"
                prev.append((x, y))
            y += 1
        if y < n - 1:
            y += 1
            if maze[x][y] == ".":
                maze[x][y] = "+"
                prev.append((x, y))
            y -= 1
        while prev:
            for x, y in prev:
                if x:
                    x -= 1
                    if maze[x][y] == ".":
                        maze[x][y] = "+"
                        new.append((x, y))
                    x += 1
                else:
                    return res
                if x < m - 1:
                    x += 1
                    if maze[x][y] == ".":
                        maze[x][y] = "+"
                        new.append((x, y))
                    x -= 1
                else:
                    return res
                if y:
                    y -= 1
                    if maze[x][y] == ".":
                        maze[x][y] = "+"
                        new.append((x, y))
                    y += 1
                else:
                    return res
                if y < n - 1:
                    y += 1
                    if maze[x][y] == ".":
                        maze[x][y] = "+"
                        new.append((x, y))
                    y -= 1
                else:
                    return res
            prev.clear()
            prev.extend(new)
            new.clear()
            res += 1
        return -1

Explain

本题解采用广度优先搜索（BFS）算法，从入口开始探索迷宫，直到找到边界上的一个空格子作为出口。首先，将入口标记为已访问（用'+'替代'.'），以避免重复访问。然后，从入口开始，对周围的格子进行检查，如果是空格子并且位于边界，则直接返回结果；否则，将该格子标记为已访问，并将其加入队列中。接下来，对队列中的格子依次执行上述操作，直到队列为空或找到出口。如果无法到达任何出口，返回-1。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m = len(maze)  # 迷宫的行数
        n = len(maze[0])  # 迷宫的列数
        res = 1  # 初始化步数计数
        x, y = entrance  # 入口位置
        prev = []  # 当前层待检查的格子
        new = []  # 下一层待检查的格子

        maze[x][y] = '+'  # 标记入口为已访问
        # 检查入口的四个方向
        if x:
            x -= 1
            if maze[x][y] == '.':
                maze[x][y] = '+'
                prev.append((x, y))
            x += 1
        if x < m - 1:
            x += 1
            if maze[x][y] == '.':
                maze[x][y] = '+'
                prev.append((x, y))
            x -= 1
        if y:
            y -= 1
            if maze[x][y] == '.':
                maze[x][y] = '+'
                prev.append((x, y))
            y += 1
        if y < n - 1:
            y += 1
            if maze[x][y] == '.':
                maze[x][y] = '+'
                prev.append((x, y))
            y -= 1
        # 使用BFS找到最近的出口
        while prev:
            for x, y in prev:
                if x:  # 向上移动
                    x -= 1
                    if maze[x][y] == '.':
                        maze[x][y] = '+'
                        new.append((x, y))
                    x += 1
                else:
                    return res  # 如果已经在边界，返回步数
                if x < m - 1:  # 向下移动
                    x += 1
                    if maze[x][y] == '.':
                        maze[x][y] = '+'
                        new.append((x, y))
                    x -= 1
                else:
                    return res
                if y:  # 向左移动
                    y -= 1
                    if maze[x][y] == '.':
                        maze[x][y] = '+'
                        new.append((x, y))
                    y += 1
                else:
                    return res
                if y < n - 1:  # 向右移动
                    y += 1
                    if maze[x][y] == '.':
                        maze[x][y] = '+'
                        new.append((x, y))
                    y -= 1
                else:
                    return res
            prev.clear()  # 清空当前层
            prev.extend(new)  # 将新层设为当前层
            new.clear()  # 清空新层
            res += 1  # 步数增加
        return -1  # 如果没有找到出口，返回-1

Explore

在BFS中清空当前层的列表并更新为新层是为了保持层次遍历的清晰结构。这种处理方式确保了每一次循环中只处理当前层的节点，并且在处理完所有当前层的节点后，再集中处理下一层的节点。这样做的优点包括：1) 结构清晰易于理解，每层的处理被清晰隔离；2) 便于计算从起点到当前节点的距离，因为每完成一层的处理，步数就统一增加1，这对于寻找最短路径问题特别有用。

在题解代码中，每次在处理节点时，首先会检查节点是否位于边界上（即是否在迷宫的四周）。这是在代码的各个分支中实现的：例如，在向上移动时，如果`x`为0，表示当前格子已在最上边界，此时会直接返回`res`，即当前的步数。类似的检查也发生在向左、向右和向下移动时，如果`y`为0或`y`为`n-1`，或者`x`为`m-1`，分别表示当前格子已在左、右或下边界。

使用'+'标记已访问的格子可以有效地避免在BFS过程中重复访问同一个格子，这对于防止无限循环和减少不必要的计算非常关键。此外，这种方法也有助于确保算法的结果正确性，因为它确保每个格子只被计算一次，从而保证找到的是最短路径。在效率方面，这种标记方法直接修改了迷宫数组，避免了额外的空间开销，如使用独立的访问数组等，因此在空间利用上更为高效。

在题解中，初始化步数为1是因为算法从入口开始做第一次移动即计算为一步。这是基于入口自身不计入步数，只有从入口开始移动时才开始计数的考虑。这种初始化方式通常适用于需要计算从一个点到另一个点的最小步数的场景。然而，这种初始化可能导致问题如果算法或问题的描述中入口处本身就被认为是第一步或需要计入步数时，此时初始化应为0。此外，如果迷宫中入口即出口的情况没有被特殊处理，这种初始化也可能导致错误的步数计算。