Chương trình đếm số đảo trong ma trận nhị phân bằng Python

Cho ma trận nhị phân, đếm số đảo (nhóm các ô 1 liên thông theo 4 hướng, bao quanh bởi 0).

Ví dụ ma trận 6x5 cho kết quả 4 đảo.

Quy trình giải quyết (DFS)

1. Định nghĩa hàm explore(row, col, matrix):
2. Nếu ngoài phạm vi hoặc ô là 0, trả về.
3. Đánh dấu ô thành 0 (đã thăm).
4. Đệ quy 4 hướng: trên, dưới, trái, phải.
5. Duyệt toàn bộ ma trận, mỗi khi gặp 1, tăng đếm đảo và gọi explore.

Ví dụ mã nguồn

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

Đầu vào

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

Đầu ra

4