为何我的BFS实现超时，而相似实现却能通过？

我在解决LeetCode的最短路径二进制矩阵问题时，自己实现的BFS代码在大输入下超时（TLE），但另一版相似的代码却能通过测试，想知道是什么原因拖慢了我的代码。

我的代码：

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:

        if grid[0][0] == 1:
            return -1
        M=len(grid)-1
        seen = set()
        q = deque([])
        res = float('inf')
        q.append((0,0,1))

        while q:
            r,c, curr = q.popleft()
            if r==M and c==M:
                return curr
            directions = [[1,0], [0,1], [1,1], [-1,0], [0,-1], [-1,-1], [1, -1], [-1, 1]]
            seen.add((r,c))
            for ro, co in directions:
                nr, nc = r+ro, c+co
                if (nr,nc) in seen or nr < 0 or nc < 0 or nr > M or nc > M or grid[nr][nc] == 1:
                    continue
                q.append((nr,nc,curr+1))
        return -1

可以通过的相似代码：

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        N = len(grid)
        q = deque([(0, 0, 1)]) # r, c, length
        visit = set((0, 0))
        direct = [[0, 1], [1, 0], [0, -1], [-1, 0],
                  [1, 1], [-1, -1], [1, -1], [-1, 1]]
        while q:
            r, c, length = q.popleft()
            if (min(r, c) < 0 or max(r, c) >= N or
                grid[r][c]):
                continue
            if r == N - 1 and c == N - 1:
                return length
            for dr, dc in direct:
                if (r + dr, c + dc) not in visit:
                    q.append((r + dr, c + dc, length + 1))
                    visit.add((r + dr, c + dc))
        return -1

你的代码超时主要有两个核心问题：

1. 已访问节点的标记时机错误 #

你的代码在出队后才将当前节点加入seen集合，这会导致同一个节点被多次加入队列。比如，当多个不同的邻居节点都能到达同一个未被标记的节点时，这些邻居都会把该节点重复添加到队列中，队列规模会迅速膨胀，后续需要处理大量重复节点，直接拖慢整体运行速度。

而通过的代码在入队前就将节点标记为已访问（visit.add((r + dr, c + dc))），每个节点只会被加入队列一次，从根源上避免了重复处理，这是性能差异的最关键原因。

2. 方向列表的重复创建 #

你把directions列表的定义放在了while循环内部，这意味着每次循环迭代都会重新创建这个包含8个元素的列表。虽然单次创建开销很小，但大网格场景下循环次数可能达到数万甚至数十万次，累积的额外内存分配和初始化开销会显著增加运行时间。

通过的代码将direct列表定义在循环外部，只创建一次，避免了重复创建的开销。

次要影响：边界与合法性检查的时机 #

你的代码在遍历邻居时才检查边界和网格值，而通过的代码在出队后先检查当前节点是否合法（比如越界或为1）。不过这个差异对性能的影响远小于前两点，属于可优化的细节。

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