20456: 统计封闭岛屿的数目

http://cs101.openjudge.cn/practice/20456/

给定10行，每行有10个数字的方形地图，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。如果一座岛屿完全由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为「封闭岛屿」。请输出封闭岛屿的数目。

输入

10行，每行有10个数字(0或1)

输出

一个整数，封闭岛屿的数目

样例输入

1,0,0,0,0,0,1,0,1,0
1,1,1,1,1,0,0,0,0,0
1,0,0,0,1,1,1,1,0,0
1,0,0,1,0,1,0,1,1,0
1,0,0,0,0,1,0,1,0,0
0,0,1,0,0,0,0,1,0,0
1,1,1,0,0,0,0,0,0,0
1,0,1,1,0,0,1,1,1,0
1,0,1,0,0,1,0,0,1,0
0,0,0,0,0,0,1,1,1,1

样例输出

提示

1个封闭岛屿

python

def closedIsland(grid):
    rows, cols = len(grid), len(grid[0])

    # 检查岛屿是否封闭的DFS函数
    def dfs(r, c):
        if grid[r][c] == 1:
            return True
        if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
            return False
        
        # 标记当前单元格为已访问
        grid[r][c] = 1
        
        # 检查所有方向
        up = dfs(r - 1, c)
        down = dfs(r + 1, c)
        left = dfs(r, c - 1)
        right = dfs(r, c + 1)
        
        return up and down and left and right

    closed_islands = 0
    for r in range(1, rows - 1):  # 从1开始，忽略边界
        for c in range(1, cols - 1):  # 从1开始，忽略边界
            if grid[r][c] == 0 and dfs(r, c):
                closed_islands += 1

    return closed_islands

# 读取输入
grid = []
for _ in range(10):
    row = list(map(int, input().split(',')))
    grid.append(row)

# 输出结果
print(closedIsland(grid))

20456: 统计封闭岛屿的数目 ​

20456: 统计封闭岛屿的数目