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

1.题目基本信息

1.1.题目描述

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

1.2.题目地址

https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/

2.解题方法

2.1.解题思路

广度优先搜索

2.2.解题步骤

第一步，构建广度优先搜索的队列

第二步，初始化entrance入口的已访问状态

第三步，BFS模板进行BFS遍历，并记录BFS的层数，BFS遍历找到出口时退出遍历，此时的层数即为步数；如果遍历完后，还是没找到结果，则返回-1

3.解题代码

Python代码

from collections import dequeclass Solution:def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:rows,cols=len(maze),len(maze[0])directs=[[-1,0],[0,-1],[1,0],[0,1]]# 第一步，构建广度优先搜索的队列entrance=tuple(entrance)que=deque([entrance])# 第二步，初始化entrance入口的已访问状态maze[entrance[0]][entrance[1]]="+"  # 初始化entrance为已经访问过result=0    # BFS遍历的层数# 第三步，BFS模板进行BFS遍历，并记录BFS的层数，BFS遍历找到出口时退出遍历，此时的层数即为步数；如果遍历完后，还是没找到结果，则返回-1while que:curLength=len(que)for _ in range(curLength):x,y=que.popleft()for direct in directs:nx,ny=x+direct[0],y+direct[1]npoint=(nx,ny)if 0<=nx<rows and 0<=ny<cols and maze[nx][ny]!="+":que.append(npoint)maze[nx][ny]="+"  # 标记为已经参观过了（这里需要在入队前添加到已访问状态中，如果在pop处加入已访问状态，将导致队列中出现很多重复的元素，导致超时）if nx in [0,rows-1] or ny in [0,cols-1]:return result+1result+=1return -1

4.执行结果