Chương trình tìm đảo lớn nhất sau khi đổi một ô nước thành đất trong Python

Cho ma trận nhị phân: 1 là đất, 0 là nước. Đảo là nhóm 1 liên thông (4 hướng). Có thể đổi tối đa một ô nước thành đất. Tìm kích thước đảo lớn nhất có thể đạt được.

Ví dụ ma trận 4x3 cho kết quả 7 (nối hai đảo lớn bằng cách đổi một ô nước).

Giải pháp

Sử dụng Flood Fill (DFS) để gán ID và tính diện tích từng đảo:

• Duyệt ma trận, flood fill các ô 1 chưa thăm, gán ID duy nhất, lưu diện tích vào mass[ID]
• ans = max(diện tích các đảo, 1)
• Duyệt mỗi ô nước (0), xem 4 hướng lân cận, thu thập set các ID đảo liền kề
• Cập nhật ans = max(ans, 1 + tổng diện tích các đảo liền kề)

Ví dụ minh họa

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] = mass.get(id, 0) + 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))

Đầu vào

[[1, 0, 1], [0, 0, 0], [1, 1, 0], [1, 1, 1]]

Đầu ra

7