1926. 迷宫中离入口最近的出口

给你一个 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 中等

代码

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        '''“.”是空格，“+”是墙，迷宫的出口就是矩阵的边界，入口不算出口'''
        m, n = len(maze), len(maze[0])
        queue = deque([entrance])
        visited = [[False]*(n) for _ in range(m)]
        step = 0
        visited[entrance[0]][entrance[1]] = True
        while queue:
            for _ in range(len(queue)):
                [x, y] = queue.popleft()              
                if x > 0 and not visited[x-1][y] and maze[x-1][y] != '+':
                    if x - 1 == 0 or y == 0 or y == n-1:
                        return step + 1
                    queue.append([x-1,y])
                    visited[x-1][y] = True

                if y > 0 and not visited[x][y-1] and maze[x][y-1] != '+':
                    if x == 0 or y - 1 == 0 or x == m-1:
                        return step + 1
                    queue.append([x,y-1])
                    visited[x][y-1] = True
                    
                if x < m-1 and not visited[x+1][y] and maze[x+1][y] != '+':
                    if y == 0 or x + 1 == m-1 or y == n-1:
                        return step + 1
                    queue.append([x+1,y])
                    visited[x+1][y] = True

                if y < n-1 and not visited[x][y+1] and maze[x][y+1] != '+':
                    if x == 0 or x == m-1 or y + 1 == n-1:
                        return step + 1
                    queue.append([x,y+1])
                    visited[x][y+1] = True
            step += 1
        return -1