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

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程