假设我们有一个二元矩阵，其中1代表土地，0代表水。一个岛屿是由水包围的一组1。我们必须找到最大的岛屿的大小。我们最多只能将一个水单元更改为陆单元。
所以，如果输入像
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
则输出将为7，因为我们可以将一个水单元降落以连接两个岛屿。所以最终矩阵就像-
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
为了解决这个问题，我们将遵循以下步骤-
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