二维数组中的孔数(Python)

Question

考虑一个二进制二维数组。我试图计算连接零的数量，这样由这些零创造的形状就完全被1s包围了(因此，不在边界上)。我只需要知道数组中是否至少存在一个洞。

洞的例子:

1 hole
111
101
101
111
1 hole
0000
1011
0110
1001
1011
1110

无效的孔洞示例:

101
111
001
01111
11001
10001
10001
10011
10111

我已经研究了"岛屿数量"问题和连接组件，但我似乎找不到一种方法来适应这个问题。我遇到的主要问题是确保当0的集合包含一个边界数字时，它仍然被算作一个洞。

有谁知道解决这个问题的正确方向是什么吗?

Answer 1

这是一个完整的Python程序:

input = """0100
1011
0110
1011
1001
1110"""
grid = input.splitlines()
holes = 0
seen = set()
def is_in_hole(x, y):
'''dfs'''
seen.add((x, y))
if grid[y][x] != '0': return True
if y in [0, len(grid) - 1] or x in [0, len(grid[0]) - 1]: return False
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nei_x, nei_y = x + dx, y + dy
if (nei_x, nei_y) in seen: continue
seen.add((nei_x, nei_y))
if not is_in_hole(nei_x, nei_y): return False
return True
for y in range(1, len(grid) - 1):
for x in range(1, len(grid[0]) - 1):
if (x, y) not in seen and grid[y][x] == '0': 
if is_in_hole(x, y): holes += 1
print(holes)