BFS实现岛屿数量统计的Python代码错误排查

问题规则说明 #

给定表示水陆分布的二维网格，岛屿统计遵循以下规则：

• 网格中元素"1"代表陆地，"0"代表水域
• 二维数组边界外的区域默认视为水域，被水域完全包围的陆地即为岛屿
• 仅上下左右四个方向相连的陆地，算作同一个岛屿的陆地块

示例输入 #

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

示例预期输出 #

3

故障代码 #

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

        def bfs(r,c):
            q = collections.deque()
            visited.add((r,c))
            q.append([r,c])
            while q:
                a = q.popleft()
                r = a[0]
                c = a[1]
                if r-1  >= 0 :
                    if (r-1,c) not in visited:
                        q.append([r-1,c])
                        visited.add((r-1,c))
                if r+1 <= rows-1:
                    if (r+1,c) not in visited:
                        q.append([r+1,c])
                        visited.add((r+1,c))
                if c-1 >= 0:
                    if (r,c-1) not in visited:
                        q.append([r,c-1])
                        visited.add((r, c-1))
                if c+1 <= cols-1:
                    if (r,c+1) not in visited:
                        q.append([r,c+1])
                        visited.add((r,c+1))
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r,c) not in visited:
                    bfs(r,c)
                    amount_islands += 1
        return amount_islands

初始问题现象 #

代码采用BFS逻辑实现遍历：循环中弹出队列队首元素，查找边界合法的相邻节点后加入队列并标记为已访问，但运行后无法得到预期的正确结果，最初怀疑参考的通用图BFS遍历逻辑存在问题。

问题根因（自查确认） #

参考的通用BFS实现逻辑本身没有错误，故障核心原因是：将相邻节点加入BFS队列时，未校验对应节点是陆地还是水域，导致代表水域的"0"节点也被错误加入岛屿的遍历队列，打乱了陆地块的遍历逻辑，最终岛屿计数结果错误。
修复方案：在判断四个方向的相邻节点时，除了校验节点是否在网格边界内、是否已被访问，还需要额外校验grid[邻接节点行坐标][邻接节点列坐标] == "1"，确认节点属于陆地后，再将其加入队列、标记为已访问。

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