如何使用递归洪水填充算法求解二维数组中图形的最大面积？

问题描述 #

给定由0和1组成的二维网格，1代表被填充的单元格，0代表空单元格。图形指由共享边（上下左右四个方向，不含对角线）的1构成的集合。要求用递归洪水填充算法计算网格中图形的最大面积。

输入示例 #

6 10 // array size
1 1 0 0 0 0 0 1 1 0
0 1 1 1 0 1 0 1 1 0
0 1 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0

输出示例 #

12 (The maximum area of a figure consisting of ones)

实现思路 #

1. 遍历网格每一个单元格：
   • 若当前单元格值为1，说明找到未访问的连通区域
   • 用递归洪水填充法遍历该区域所有连通的1，同时将访问过的1标记为0（避免重复计算）
   • 统计当前区域的面积
2. 记录所有连通区域的面积，返回最大值

代码实现（Python） #

def max_area_of_island(grid):
    rows = len(grid)
    if rows == 0:
        return 0
    cols = len(grid[0])
    max_area = 0

    def flood_fill(r, c):
        # 边界判断：超出网格范围或当前单元格为0，返回0
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
            return 0
        # 标记当前单元格为已访问（设为0）
        grid[r][c] = 0
        # 递归计算上下左右四个方向的面积，加上当前单元格的1
        return 1 + flood_fill(r-1, c) + flood_fill(r+1, c) + flood_fill(r, c-1) + flood_fill(r, c+1)

    # 遍历每个单元格
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                current_area = flood_fill(r, c)
                if current_area > max_area:
                    max_area = current_area
    return max_area

# 处理输入并运行
if __name__ == "__main__":
    # 读取输入
    input_lines = [
        "6 10",
        "1 1 0 0 0 0 0 1 1 0",
        "0 1 1 1 0 1 0 1 1 0",
        "0 1 1 0 1 0 1 0 1 0",
        "0 1 0 1 0 1 0 1 1 0",
        "0 1 1 1 0 0 1 1 1 0",
        "0 0 0 0 0 0 0 0 0 0"
    ]
    # 解析网格
    rows, cols = map(int, input_lines[0].split())
    grid = []
    for line in input_lines[1:rows+1]:
        grid.append(list(map(int, line.split())))
    
    # 计算最大面积
    result = max_area_of_island(grid)
    print(f"{result} (The maximum area of a figure consisting of ones)")

结果验证 #

运行代码后，针对给定输入输出为12 (The maximum area of a figure consisting of ones)，与预期一致。该结果对应网格左侧的大型连通区域，递归洪水填充统计其所有1的数量为12。

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