資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢更改一個水單元格為陸地單元格後的最大島嶼
假設我們有一個二進位制矩陣，其中 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 := mat 的行數，C := mat 的列數
mass := 一個新的對映
id := 555
定義一個函式 floodfill()。這將採用 r、c、id
如果 r 和 c 在矩陣範圍內並且 mat[r, c] 為 1，則
mat[r, c] := id
mass[id] := mass[id] + 1
對於 [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ] 中的每一對 (r2, c2)，執行以下操作：
floodfill(r2, c2, id)
從主方法執行以下操作：−
對於從 0 到 R 的範圍內的 r，執行以下操作：
對於從 0 到 C 的範圍內的 c，執行以下操作：
如果 mat[r, c] 等於 1，則
id := id + 1
mass[id] := 0
floodfill(r, c, id)
ans := (所有 mass 值和 1) 中的最大值
對於從 0 到 R − 1 的範圍內的 r，執行以下操作：
對於從 0 到 C − 1 的範圍內的 c，執行以下操作：
如果 mat[r, c] 不等於 0，則
轉到下一次迭代
island_set := 一個新的集合
對於 [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ] 中的每一對 (r2, c2)，執行以下操作：
如果 r2 和 c2 在 mat 的範圍內並且 mat[r2, c2] 為 1，則
將 mat[r2, c2] 新增到 island_set 中
ans := ans 和 (1 + 每個島嶼在 island_set 中的每個 mass[island] 的總和) 中的最大值
返回 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
131 次檢視
