LeetCode 200.岛屿数量：BFS中Set插入位置引发TLE问题咨询

我在用BFS解决LeetCode「岛屿数量」问题时遇到了超时（TLE）问题：当在BFS循环内弹出元素后再将坐标加入visited集合时，代码无法通过测试；但如果在将坐标加入队列的同时就标记为已访问，就能顺利通过。

超时的代码实现 #

def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(r, c):
            q = [(r,c)]
            while q:
                row, col = q.pop(0)
                visited.add((row, col))  ## 这行导致超时
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for dr, dc in directions:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == "1" and
                        (r,c) not in visited):
                        q.append((r,c))

        for r in range(rows):
            for c in range(cols):
                if (r,c) not in visited and grid[r][c] == "1":
                    bfs(r,c)
                    islands += 1
        return islands

可通过的代码实现 #

def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(r, c):
            q = [(r,c)]
            visited.add((r, c)) # 提前标记当前坐标为已访问
            while q:
                row, col = q.pop(0)
                # visited.add((row, col)) ## 注释掉这行
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for dr, dc in directions:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == "1" and
                        (r,c) not in visited):
                        q.append((r,c))
                        visited.add((r, c)) ## 在加入队列时标记已访问

        for r in range(rows):
            for c in range(cols):
                if (r,c) not in visited and grid[r][c] == "1":
                    bfs(r,c)
                    islands += 1
        return islands

问题原因分析 #

核心差异在于标记已访问的时机，直接影响了队列的冗余程度：

• 第一种写法中，只有当元素被弹出队列时才标记为已访问。这会导致同一个陆地坐标被多个相邻的陆地重复加入队列——比如坐标B相邻于A和C，当处理A时会把B加入队列，此时B还没被标记为已访问；处理C时又会把B再次加入队列。最终队列里会充斥大量重复元素，每次弹出处理都是冗余操作，时间复杂度急剧上升，触发超时。
• 第二种写法在将坐标加入队列的同时就标记为已访问，确保每个坐标只会被加入队列一次，从根源上避免了重复处理，队列规模始终保持合理，效率自然达标。

你可能误以为队列里只会有陆地元素就不会有问题，但即使都是陆地，未及时标记已访问会导致同一个元素被多次入队，引发大量无效计算，最终拖垮性能。

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