连通域算法返回每个连通域面积

以下是一个Python实现，使用深度优先搜索（DFS）遍历连通域并计算面积：

def get_connected_areas(grid):
    # grid是一个二维列表，每个元素为0或1，表示一个二值化图像

    def dfs(r, c, area):
        # 递归遍历当前连通域
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0:
            # 超出边界或当前格子为0，返回
            return
        grid[r][c] = 0  # 将当前格子标记为已访问
        area[0] += 1  # 更新面积
        # 递归遍历四个方向
        dfs(r-1, c, area)
        dfs(r+1, c, area)
        dfs(r, c-1, area)
        dfs(r, c+1, area)

    areas = []  # 存储所有连通域的面积
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                # 发现一个新的连通域
                area = [0]  # 使用可变对象传递参数
                dfs(r, c, area)
                areas.append(area[0])
    return areas

使用示例：

grid = [
    [1, 0, 1, 0, 0],
    [1, 1, 0, 0, 1],
    [0, 1, 0, 1, 1],
    [0, 1, 0, 0, 0],
    [1, 1, 0, 1, 1]
]
areas = get_connected_areas(grid)
print(areas)  # 输出 [7, 3, 4, 3, 6]

该算法的时间复杂度为$O(nm)$，其中$n$和$m$分别为二维列表的行数和列数。