在Python中将一个水单元更改为陆地单元后找到最大岛屿的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个二元矩阵，其中1代表土地，0代表水。一个岛屿是由水包围的一组1。我们必须找到最大的岛屿的大小。我们最多只能将一个水单元更改为陆单元。

所以，如果输入像

101
000
110
111

则输出将为7，因为我们可以将一个水单元降落以连接两个岛屿。所以最终矩阵就像-

101
000
110
111

为了解决这个问题，我们将遵循以下步骤-

  • R：=垫子的行数，C：=垫子的列数

  • 质量：=新映射

  • id：= 555

  • 定义一个功能floodfill()。这将需要r，c，id

  • 如果r和c在矩阵范围内并且mat [r，c]为1，则

    • Floodfill(R2,C2,ID)

    • mat [r，c]：= id

    • 质量[ID]：=质量[ID] + 1

    • 对于[[r + 1，c），（r − 1，c），（r，c +1），（r，c − 1）]中的每一对(r2,c2)

    • 从主要方法中执行以下操作-

    • 对于0到R范围内的r，执行

      • 如果mat [r，c]与1相同，则

      • id：= id + 1

      • mass [id]：= 0

      • floodfill(r, c, id)

      • 对于0到C范围内的c，执行

      • ans：=的最大值（质量和1的所有值）

      • 对于0到R − 1范围内的r

        • 如果mat [r，c]不等于0，则

        • island_set：=一个新集合

        • 对于[[r + 1，c），（r − 1，c），（r，c +1），（r，c − 1）]中的每一对(r2,c2)

        • 进行下一次迭代

        • 将mat [r2，c2]添加到island_set

        • 如果r2和c2在mat的范围内，并且mat [r2，c2]为1，则

        • ans：= ans的最大值和（1 + island_set中每个岛的所有质量[岛]的总和）

        • 对于0到C − 1范围内的c

        • 返回ans

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

        示例

        class Solution:
           def solve(self, mat):
              R, C = len(mat), len(mat[0])
              mass = {}
              id = 555
              def floodfill(r, c, id):
                 nonlocal R, C, mat, mass
                 if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
                    mat[r][c] = id
                    mass[id] += 1
                    for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),
                       (r, c − 1)]:
                       floodfill(r2, c2, id)
                          for r in range(R):
              for c in range(C):
                 if mat[r][c] == 1:
                    id += 1
                    mass[id] = 0
                    floodfill(r, c, id)
              ans = max([val for val in mass.values()] + [1])
              for r in range(R):
                 for c in range(C):
                    if mat[r][c] != 0:
                       continue
                    island_set = set()
                    for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),(r, c − 1)]:
                       if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                          island_set.add(mat[r2][c2])
                       ans = max(ans, 1 + sum([mass[island] for island in island_set]))
                 return ans
        ob = Solution()
        matrix = [
           [1, 0, 1],
           [0, 0, 0],
           [1, 1, 0],
           [1, 1, 1]
        ]
        print(ob.solve(matrix))

        输入值

        [
        [1, 0, 1],
        [0, 0, 0],
        [1, 1, 0],
        [1, 1, 1] ]
        输出结果
        7

        以上是 在Python中将一个水单元更改为陆地单元后找到最大岛屿的程序 的全部内容， 来源链接： utcz.com/z/348741.html

        回到顶部