Chương trình đếm số đảo hoàn toàn bị bao quanh trong ma trận bằng Python

Cho ma trận nhị phân: 1 (đất), 0 (nước). Đảo là nhóm 1 liên thông 4 hướng, bị bao quanh hoàn toàn bởi nước. Đếm số đảo như vậy.

Ví dụ: ma trận 6x5 → 2 đảo bị bao quanh.

Giải thuật

• DFS từ mỗi ô đất chưa thăm: nếu DFS chạm biên ma trận → không bị bao quanh (trả về False).
• Đánh dấu ô đã thăm bằng gán 0.
• Đảo bị bao quanh khi 4 hướng DFS đều trả về True.
• Đếm số lần DFS trả về True.

Ví dụ minh họa

class Solution:
    def solve(self, matrix):
        def dfs(i, j):
            if i < 0 or j < 0 or i >= R or j >= C:
                return False
            if matrix[i][j] == 0:
                return True
            matrix[i][j] = 0
            a = dfs(i+1, j)
            b = dfs(i-1, j)
            c = dfs(i, j+1)
            d = dfs(i, j-1)
            return a and b and c and d
        R, C = len(matrix), len(matrix[0])
        ans = 0
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 1:
                    if dfs(i, j):
                        ans += 1
        return ans

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

Đầu vào

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

Đầu ra

2