LeetCode 5793.迷宫中入口最近的出口

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

解题思路：

该题是比较明显的使用广度优先搜索的题目，我们可以从起点开始进行BFS，直到找到出口或者结束搜索，但是在这道题中需要非常注意对已经搜索过的位置的处理和往队列中增加下一个搜索点的处理。我们需要在往队列中增加新的搜索点之前对其进行判断，是否已经是出口，同时将其直接标记成已访问，这样才能最大化的降低某些节点出现重复访问的情况，AC代码如下：

import collections


class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m = len(maze)
        n = len(maze[0])
        stack = collections.deque()
        stack.append((entrance[0], entrance[1], 0))
        maze[entrance[0]][entrance[1]] = "+"
        while stack:
            row, col, ans = stack.popleft()
            maze[row][col] = "+"
            for x, y in (0, 1), (0, -1), (1, 0), (-1, 0):
                dx = row + x
                dy = col + y
                if 0 <= dx < m and 0 <= dy < n and maze[dx][dy] == ".":
                    if (dx == 0 or dy == 0 or dx == m - 1 or dy == n - 1):
                        return ans + 1
                    maze[dx][dy] = "+"
                    stack.append((dx, dy, ans + 1))
        return -1