用Python删除所有完全被水包围的岛的程序
假设我们有一个二元矩阵，其中1代表土地，0代表水。岛屿是由1组成的一组，被0（水）或边缘包围。我们必须找到所有被水完全包围的岛屿，并将它们修改为0。我们知道，如果所有邻居（水平和垂直而不是对角线）均为0（所有邻居都不是边），那么一个岛屿就完全被水包围了。
所以，如果输入像
那么输出将是
示例
让我们看下面的实现以更好地理解-
from collections import deque
class Solution:
def solve(self, A):
row = len(A)
col = len(A[0])
B = [[0 for _ in range(col)] for _ in range(row)]
seen = set()
def nei(i, j):
if i + 1 < row and A[i + 1][j]:
yield (i + 1, j)
if j + 1 < col and A[i][j + 1]:
yield (i, j + 1)
if i - 1 >= 0 and A[i - 1][j]:
yield (i - 1, j)
if j - 1 >= 0 and A[i][j - 1]:
yield (i, j - 1)
for i in range(row):
for j in range(col):
if i not in (0, row - 1) and j not in (0, col - 1):
continue
if (i, j) in seen:
continue
if A[i][j] == 0:
continue
d = deque([(i, j)])
while d:
x, y = d.popleft()
B[x][y] = 1
for x2, y2 in nei(x, y):
if (x2, y2) not in seen:
d.append((x2, y2))
seen.add((x2, y2))
return B
ob = Solution()
matrix = [
[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1],
]
print(ob.solve(matrix))输入值
[ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1], ]输出结果
[ [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1] ]