BFS实现最大岛屿面积计算输出结果异常的逻辑问题排查

问题基本信息 #

• 题目规则：网格中1代表陆地，0代表水域，陆地仅可通过上、下、左、右四个方向连通，需计算网格中最大岛屿的面积
• 测试输入网格：

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

• 预期输出：最大岛屿面积为6
• 实际运行结果：现有BFS代码返回值为3

问题代码 #

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    rowlen  = len(grid)
    collen = len(grid[0])
    q = collections.deque()
    visited = set()
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    islandsize = []
    if not grid:
        return 0

    def bfs(i,j):
        size = 1
        q.append((i,j))
        visited.add((i,j))
        while q:
            square = q.popleft()
            for x,y in directions:
                newx = square[0] + x
                newy = square[1] + y
                if newx in range(rowlen) and newy in range(collen) and grid[newx][newy] == 1 and (newx,newy) not in visited:
                    q.append((i,j))  # 错误行
                    size += 1
                    visited.add((newx,newy))
        islandsize.append(size)

    for i in range(rowlen):
        for j in range(collen):
            if grid[i][j] == 1 and (i,j) not in visited:
                bfs(i,j)
    if not islandsize or max(islandsize) == 0: 
        return 0 
    else:
        return max(islandsize)

错误定位 #

核心bug出在BFS的入队操作：
当校验通过，确认(newx, newy)是未访问的陆地时，你入队的参数是BFS起始点(i,j)，而非新发现的陆地坐标(newx, newy)。
这个错误会直接打断BFS的层序遍历逻辑：

• 队列中只会反复存入、取出起始点坐标
• 新发现的陆地虽然被标记为已访问、被计入size，但从来没有被作为遍历节点处理，它周围连通的其他陆地永远不会被搜索到
• 最终统计的岛屿面积仅包含「BFS起始点 + 起始点直接相邻的陆地」，自然无法得到正确的6，只会返回起始点周围直接邻接的陆地总数加1，也就是你看到的3。

修复方案 #

不需要改动整体BFS实现思路，仅需要把错误行的入队参数替换为新发现的陆地坐标即可，修改后对应代码段为：

if newx in range(rowlen) and newy in range(collen) and grid[newx][newy] == 1 and (newx,newy) not in visited:
    q.append((newx, newy))  # 入队新发现的邻接陆地坐标
    size += 1
    visited.add((newx,newy))

修改后运行测试用例即可得到正确结果6。

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