Chương trình tìm diện tích đảo lớn nhất trong ma trận trong Python

Mô tả bài toán

Cho ma trận nhị phân (1: đất, 0: nước). Đảo là nhóm các ô 1 kề nhau (4 hướng). Tìm diện tích đảo lớn nhất.

Ví dụ: ma trận 6x7 như hình → đầu ra 6.

Giải thuật (DFS đệ quy)

1. Định nghĩa dfs(matrix, r, c):
   • Tăng total, đánh dấu matrix[r][c] = 0.
   • Đệ quy 4 hướng nếu trong phạm vi và giá trị 1.
2. Duyệt toàn bộ ma trận, khi gặp 1: đặt total=0, gọi dfs, cập nhật max_island.
3. Trả về max_island.

Ví dụ mã Python

class Solution:
    def solve(self, matrix):
        self.r_len = len(matrix)
        self.c_len = len(matrix[0])
        max_island = 0
        for r in range(self.r_len):
            for c in range(self.c_len):
                if matrix[r][c] == 1:
                    self.total = 0
                    self.dfs(matrix, r, c)
                    max_island = max(max_island, self.total)
        return max_island

    def dfs(self, matrix, r, c):
        self.total += 1
        matrix[r][c] = 0
        if r - 1 >= 0 and matrix[r - 1][c] == 1:
            self.dfs(matrix, r - 1, c)
        if c - 1 >= 0 and matrix[r][c - 1] == 1:
            self.dfs(matrix, r, c - 1)
        if r + 1 < self.r_len and matrix[r + 1][c] == 1:
            self.dfs(matrix, r + 1, c)
        if c + 1 < self.c_len and matrix[r][c + 1] == 1:
            self.dfs(matrix, r, c + 1)

ob = Solution()
matrix = [
    [0, 0, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 0, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 1, 0]
]
print(ob.solve(matrix))

Đầu vào

matrix = [ [0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0] ]

Đầu ra

6