LeetCode #200岛屿数量：BFS算法超时原因排查

核心问题出在两段代码对重复队列节点的处理逻辑差异，具体如下：

逻辑差异对比 #

初始正常代码的BFS逻辑 #

def bfs(i,j):
    q = deque([[i,j]])
    while q:
        r,c = q.popleft()
        # 先判断节点是否为未访问的有效陆地
        if 0<=r<len(grid) and 0<=c<len(grid[0]) and grid[r][c]=="1":
            grid[r][c]="0"
            # 直接添加四个方向到队列（不管是否有效/已访问）
            q += [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]

弹出队列节点后，先校验节点有效性和访问状态：

• 如果是未访问的陆地，标记为已访问并添加四个方向到队列；
• 如果节点已被访问（值为"0"）或越界，直接跳过所有后续操作。

修改后超时代码的BFS逻辑 #

def bfs(i,j):
    q = deque([[i,j]])
    while q:
        r,c = q.popleft()
        # 直接标记为已访问，不做任何校验
        grid[r][c]="0"
        # 遍历四个方向，仅添加有效未访问陆地到队列
        for d in [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]:
            if 0<=d[0]<len(grid) and 0<=d[1]<len(grid[0]) and grid[d[0]][d[1]]=="1":
                q.append(d)

弹出队列节点后，不做任何校验直接标记为已访问，随后强制遍历四个方向做有效性检查——哪怕当前节点已经是"0"或越界。

超时的根本原因 #

在大规模网格（比如全1的大矩阵）中，同一个陆地节点会被相邻节点多次加入队列：

• 初始代码处理这种重复节点时，后续弹出会直接跳过，不会产生任何无用操作；
• 修改后的代码处理重复节点时，哪怕节点已经是"0"，仍会执行四次边界检查和值校验，累积的无用操作会呈指数级增长，最终触发超时。

举个简单例子：假设陆地节点B被两个相邻节点A、C分别加入队列，初始代码仅在第一次弹出B时处理，第二次弹出直接跳过；修改后的代码两次弹出B都会遍历四个方向做检查，平白多了四次无效校验。

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