在Python中删除所有被水完全包围的岛屿的程序

假设我们有一个二进制矩阵，其中1表示陆地，0表示水。 岛屿是由0（水）或边界包围的1组。 我们必须找到完全由水环绕的所有岛屿，并将它们修改为0。 因为我们知道一个岛屿完全被水包围，如果所有邻居（水平和垂直而不是对角线）都是0（没有邻居是边界）。

因此，如果输入如下所示

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

为了解决这个问题，我们将按照以下步骤进行 –

• row：A的行数

• col：A的列数

• B：大小为A的矩阵，并填充为0

• seen：一个新的集合

• 对于i在范围0到row中，

  • 对于j在范围0到col中，
    • 如果i和j不在矩阵范围内，则

    • 进入下一个迭代

    • 如果（i，j）被看到，则

    • 进入下一个迭代

    • 如果 A [i，j]与0相同，则

    • 进入下一个迭代

    • d：具有一个元素（i，j）的双端队列

    • while d不为空，执行以下操作

    • （x，y）：d的左侧元素，并从d中删除

    • B [x，y] = 1

    • 对于（x，y）的每个邻居（x2，y2），执行以下操作

      • 如果（x2，y2）未被看到，则

      • 在d的末尾插入（x2，y2）

      • 标记（x2，y2）为seen

• 返回B

更多Python相关文章，请阅读：Python 教程

例子

让我们看下面的实现，以更好地理解 –

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]
]