迷宫中离入口最近的出口：BFS解法超时优化求助

我在解决LeetCode的「迷宫中离入口最近的出口」问题时，选择了BFS算法（这确实是最优思路，因为BFS天然适合找最短路径），但处理大规模输入时出现了超时错误。以下是我的原实现代码：

def insidemaze(r,c,nrow,ncol,grid):
    if (( r>=0 and r<= nrow-1 and c>=0 and c<=ncol-1)) :
        return True
    return False    

def isboundary(r,c,nrow,ncol,grid):
    if ( r== 0 or r==nrow-1 or c== 0 or c==ncol-1) :
        return True 

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        
        queue = collections.deque()
        queue.append([entrance[0],entrance[1],0])

        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        maze[entrance[0]][entrance[1]] = "+"

        nrow = len(maze)
        ncol = len(maze[0])

        while queue :
            print("queue =" , queue)
            a = queue.popleft()
            maze[a[0]][a[1]] = "+"
            for dir in dirs :
                b = [ a[0] + dir[0] , a[1] + dir[1] ]
                print("b=",b)
                if (insidemaze(b[0],b[1],nrow,ncol,maze) ) :
                    if (isboundary(b[0],b[1],nrow,ncol,maze) and (maze[b[0]][b[1]] == "." ) ) :
                        return(a[2]+1)
                    else :
                        if maze[b[0]][b[1]] == "." :
                            queue.append([b[0],b[1],a[2]+1])
                        else:
                            print("do nothing")    
        return(-1)

超时原因及优化方案 #

1. 移除调试打印语句

原代码中的print("queue =", queue)、print("b=",b)、print("do nothing")会在大规模输入时产生巨量IO操作，这是超时的主要原因之一，直接删除即可。

2. 内联判断逻辑，减少函数调用开销

单独的insidemaze和isboundary函数会带来额外的函数调用栈开销，尤其是在BFS循环中反复调用时，累积开销很大。可以直接将判断逻辑内联到代码中：

• 入迷宫判断：0 <= nr < nrow and 0 <= nc < ncol
• 边界判断：nr == 0 or nr == nrow-1 or nc == 0 or nc == ncol-1

3. 提前标记已访问节点，避免重复入队

原代码中，入口节点在入队前标记为已访问，但其他节点是在出队时才标记为"+"。这会导致同一个节点可能被多个邻居同时发现并加入队列，造成队列冗余，增加处理量。正确的做法是在入队前就标记该节点为已访问，确保每个节点只被处理一次。

4. 使用元组代替列表存储队列元素

元组比列表更轻量，访问速度更快，用元组存储队列中的坐标和步数，可以小幅提升性能。

优化后的代码 #

import collections
from typing import List

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        queue = collections.deque()
        # 用元组存储队列元素
        queue.append((entrance[0], entrance[1], 0))
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        nrow, ncol = len(maze), len(maze[0])
        # 入口标记为已访问
        maze[entrance[0]][entrance[1]] = "+"

        while queue:
            r, c, steps = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                # 内联入迷宫判断
                if 0 <= nr < nrow and 0 <= nc < ncol:
                    if maze[nr][nc] == ".":
                        # 内联边界判断，入口已标记为+，不会误判为出口
                        if nr == 0 or nr == nrow-1 or nc == 0 or nc == ncol-1:
                            return steps + 1
                        # 入队前标记已访问，避免重复入队
                        maze[nr][nc] = "+"
                        queue.append((nr, nc, steps + 1))
        return -1

优化效果说明 #

• 移除打印语句后，消除了IO瓶颈；
• 内联判断减少了函数调用开销；
• 提前标记已访问节点避免了队列冗余，大幅减少了BFS的循环次数；
• 元组的使用进一步提升了内存和访问效率。

这些优化组合起来，能有效解决大规模输入下的超时问题。

内容的提问来源于stack exchange，提问作者Siddharth Somani