โปรแกรมนับจำนวนเกาะในเมทริกซ์ใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี ต้องหาจำนวนเกาะ (islands) โดย 1 = แผ่นดิน, 0 = น้ำ เกาะคือกลุ่ม 1 ที่ติดกัน (แนวนอน/แนวตั้ง ไม่ใช่แนวทแยง) และล้อมรอบด้วยน้ำ

ตัวอย่างเมทริกซ์ 6x5 ผลลัพธ์คือ 4 เกาะ

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

1. ฟังก์ชัน explore(row, col, matrix):
   • ถ้า row, col นอกขอบเขต หรือ matrix[row][col] == 0: คืนค่า
   • matrix[row][col] = 0 (mark visited)
   • เรียก explore 4 ทิศทาง: บน, ล่าง, ซ้าย, ขวา
2. จากเมธอดหลัก:
   • ถ้า matrix ว่าง คืนค่า 0
   • islands = 0
   • วนลูปทุกเซลล์ (row, col):
     • ถ้า matrix[row][col] == 1: islands += 1, เรียก explore(row, col, matrix)
   • คืนค่า islands

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

class Solution:
    def explore(self, row, col, matrix):
        if (row < 0 or col < 0 or row > len(matrix) - 1
            or col > len(matrix[0]) - 1 or matrix[row][col] == 0):
            return
        matrix[row][col] = 0
        self.explore(row + 1, col, matrix)
        self.explore(row - 1, col, matrix)
        self.explore(row, col + 1, matrix)
        self.explore(row, col - 1, matrix)

    def solve(self, matrix):
        if not matrix:
            return 0
        islands = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == 1:
                    islands += 1
                    self.explore(row, col, matrix)
        return islands

ob = Solution()
matrix = [
    [1, 0, 1, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1],
    [1, 1, 1, 0, 1]
]
print(ob.solve(matrix))  # Output: 4

อินพุต / เอาต์พุต

Input: เมทริกซ์ 6x5 ตามตัวอย่าง

Output: 4