题解 | 分割后处理

import sys

for line in sys.stdin:

a = line.split()   

    # print(int(a[0]) + int(a[1]))

    m, n = int(a[0]), int(a[1])

    grid = []

    for _ in range(m):

        row = list(map(int, input().split()))

        grid.append(row)

    from collections import deque

    def fill_enclosed_water(grid, m, n):

        """

        填充被陆地包围的水面区域。

        """

        # 定义四个方向的移动

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # 遍历地图的边界，找到所有与边界相连的水面区域

        for i in range(m):

            for j in range(n):

                if (i == 0 or i == m - 1 or j == 0 or j == n - 1) and grid[i][j] == 0:

                    # 使用 BFS 标记与边界相连的水面区域

                    queue = deque([(i, j)])

                    grid[i][j] = -1  # 标记为已访问

                    while queue:

                        x, y = queue.popleft()

                        for dx, dy in directions:

                            nx, ny = x + dx, y + dy

                            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:

                                grid[nx][ny] = -1

                                queue.append((nx, ny))

        # 将所有未被标记的水面区域（被陆地包围）标记为陆地

        for i in range(m):

            for j in range(n):

                if grid[i][j] == 0:

                    grid[i][j] = 1

    def remove_islands(grid, m, n):

        """

        去除不与底边相连的陆地区域。

        """

        # 定义四个方向的移动

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # 从底边的陆地开始，标记所有与底边相连的陆地

        for j in range(n):

            if grid[m - 1][j] == 1:

                queue = deque([(m - 1, j)])

                grid[m - 1][j] = 2  # 标记为已访问

                while queue:

                    x, y = queue.popleft()

                    for dx, dy in directions:

                        nx, ny = x + dx, y + dy

                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:

                            grid[nx][ny] = 2

                            queue.append((nx, ny))

        # 将所有未被标记的陆地区域（岛屿）标记为水面

        for i in range(m):

            for j in range(n):

                if grid[i][j] == 1:

                    grid[i][j] = 0

    def calculate_land_area(grid, m, n):

        """

        计算去噪后的陆地面积。

        """

        area = 0

        for i in range(m):

            for j in range(n):

                if grid[i][j] == 1 or grid[i][j] == 2:

                    area += 1

        return area

    # 填充被陆地包围的水面

    fill_enclosed_water(grid, m, n)

    # 去除不与底边相连的陆地

    remove_islands(grid, m, n)

    # 计算陆地面积

    area = calculate_land_area(grid, m, n)

    # 输出结果

    print(area)