Leetcode BFS 集合插入导致 TLE（200. 岛屿数量）

Question

我正在尝试解决一个问题：在Leetcode上计算岛屿的数量，使用的是广度优先搜索（BFS）的方法。

当我在循环的开始部分把(r,c)这个坐标加入到已访问的集合时，结果在Leetcode上超时了。

上面的代码是这样的：

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))  ## This line causes TLE
                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

而如果我把(r,c)放在循环中的条件判断里加入，代码就能通过了。

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)) #Visited the current (r,c)
            while q:
                row, col = q.pop(0)
                # visited.add((row, col)) ## Commented this out
                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)) ## visited in the if-block

        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

我不明白，为什么第二种代码能通过并且更优化，队列里不管怎样总会有元素是grid[r][c] == "1"的，或者队列里只会有陆地元素。

Answer 1

在代码的第一个版本中，一个单元格只有在从队列中弹出后才会被标记为已访问。这可能导致在第一次弹出这个单元格之前，很多相同的单元格被添加到队列中。这会造成很多不必要的循环。你可以通过在广度优先搜索（BFS）循环中添加 if (row, col) in visited: continue 来让这个代码通过。

另一方面，第二个版本的代码更符合常规，它在第一次到达单元格并将其添加到队列时就立即将其标记为已访问。这确保了其他路径到达同一个单元格时，不会再向队列中添加无用的重复单元格。

另外要注意，从列表中删除第一个元素是比较慢的；所以你不应该用列表来替代真正的队列数据结构。可以使用 collections.deque 来代替。