LeetCode矩阵最近0距离问题：为何BFS无法保证最短路径？

嘿，我来帮你拆解这个问题——首先得给你吃个定心丸：多源BFS本身是完全可以保证最短路径的，你的疑惑可能是把超时的锅错甩给了BFS的原理，但其实问题大概率出在代码实现的细节上！

先明确：多源BFS为啥能保证最短路径？ #

BFS的核心逻辑是「按层遍历」：从起点出发，先处理所有距离为0的节点，再处理距离为1的，接着是距离为2的……以此类推。而多源BFS只是把所有的0（也就是所有起点）同时加入队列作为第0层，这样每个1的位置第一次被访问到的时候，必然是从最近的0过来的——因为如果存在更近的0，那这个1应该在更早的层就被那个更近的0遍历到了。所以从原理上来说，它绝对能得到最短路径。

那你的代码为啥会超时？ #

大概率是这些实现细节没做好：

• 没有标记已访问节点，导致重复入队：如果某个1的位置被多个0的方向同时“盯上”，你没提前标记它已经被处理过，就会重复把它加入队列，做大量无用功。正确的做法是，在把节点加入队列时就标记它的距离（相当于标记已访问），避免后续重复处理。
• 用了低效的队列操作：比如在Python里用list.pop(0)模拟队列，这个操作是O(n)复杂度的，当矩阵很大时，会拖慢整个程序。应该用collections.deque的popleft()，这是O(1)的高效操作。
• 初始化距离矩阵时没做优化：比如一开始把所有1的距离设为一个很大的数（或者-1），这样处理的时候只需要检查那些未被访问的节点，不用反复判断是否是0或者已经处理过。

给你一个高效的多源BFS实现示例 #

from collections import deque

def updateMatrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    q = deque()

    # 第一步：把所有0的位置加入队列，初始化距离为0
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == 0:
                dist[i][j] = 0
                q.append((i, j))
    
    # 四个相邻方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 开始多源BFS遍历
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 只处理边界内、未被访问过的节点
            if 0 <= nx < rows and 0 <= ny < cols and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    
    return dist

这个示例的关键优化点： #

1. 一开始就把所有0入队并标记距离为0，作为BFS的起始层。
2. 每次处理节点时，只对未被访问（dist[nx][ny] == -1）的邻居进行操作，确保每个节点只被处理一次。
3. 使用deque保证队列的出队操作是高效的O(1)，避免了list操作的性能瓶颈。

总结一下：多源BFS完全适配这个问题，也能保证最短路径，你的超时问题是实现细节没做到位，调整一下上面提到的点应该就能解决啦！

内容的提问来源于stack exchange，提问作者J. Doe