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

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

所以，如果输入像

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

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

• 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