在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