โปรแกรมหาพื้นที่เกาะใหญ่สุดในเมทริกซ์ใน Python

สมมติว่ามี binary matrix 1 = บก, 0 = น้ำ เกาะคือกลุ่ม 1 ที่ติดกัน 4 ทิศทาง ต้องการพื้นที่เกาะใหญ่สุด

ตัวอย่าง: เมทริกซ์ 6x7 ผลลัพธ์ 6

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน dfs(matrix, r, c):
   • total += 1, matrix[r][c] = 0
   • เรียกซ้ำ 4 ทิศทางถ้าเป็น 1
2. r_len, c_len = ขนาดเมทริกซ์, max_island = 0
3. วนทุกเซลล์ (r,c):
   • ถ้า matrix[r][c] == 1: total = 0, เรียก dfs, max_island = max(max_island, total)
4. คืน max_island

ตัวอย่างโค้ด

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))

อินพุต

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]]

เอาต์พุต

6