Chương trình Python đếm số đảo chồng lấn giữa hai bản đồ

Cho hai ma trận nhị phân mat1 và mat2 (1=đất, 0=nước). Một "đảo" là nhóm các ô 1 liên thông 4 chiều bị bao quanh bởi 0. Cần đếm số đảo xuất hiện ở chính xác cùng tọa độ trên cả hai bản đồ.

Ví dụ

mat1 = [[1,0,1],    mat2 = [[1,0,1],
        [1,0,0],           [1,0,0],
        [1,0,0]]           [1,0,1]]
Output: 2

Hai đảo chồng lấn: cột 0 (3 ô 1 dọc) và ô (0,2).

Thuật toán (DFS + Loại bỏ khác biệt)

1. Đầu tiên, xóa tất cả ô khác biệt giữa mat1 và mat2 (ô có giá trị khác nhau) bằng DFS (mark).
2. Sau đó, đếm số đảo còn lại trong mat1 (đã đồng bộ với mat2) bằng DFS.

Code Python

def solve(mat1, mat2):
    r, c = len(mat1), len(mat1[0])
    last_row, last_col = r - 1, c - 1
    
    def mark(i, j):
        """DFS xóa đảo tại (i,j) trên CẢ HAI ma trận"""
        mat1[i][j] = mat2[i][j] = 0
        # 4 hướng
        if i > 0 and (mat1[i-1][j] or mat2[i-1][j]): mark(i-1, j)
        if j > 0 and (mat1[i][j-1] or mat2[i][j-1]): mark(i, j-1)
        if j < last_col and (mat1[i][j+1] or mat2[i][j+1]): mark(i, j+1)
        if i < last_row and (mat1[i+1][j] or mat2[i+1][j]): mark(i+1, j)
    
    # Bước 1: Xóa ô khác biệt
    for i in range(r):
        for j in range(c):
            if mat1[i][j] != mat2[i][j]:
                mark(i, j)
    
    # Bước 2: Đếm đảo chung
    islands = 0
    for i in range(r):
        for j in range(c):
            if mat1[i][j]:
                islands += 1
                mark(i, j)
    
    return islands

# Test
mat1 = [[1,0,1],[1,0,0],[1,0,1]]
mat2 = [[1,0,1],[1,0,0],[1,0,0]]
print(solve(mat1, mat2))  # 2

Giải thích logic

Bước 1: Xóa khác biệt

Ô (2,2): mat1=1, mat2=0 → khác nhau → mark(2,2) xóa toàn bộ đảo chứa ô này trên CẢ HAI ma trận. Đảo cột 2 mat1 bị xóa hết.

Bước 2: Đếm đảo chung

Duyệt mat1 (đã đồng bộ mat2), mỗi lần gặp 1 → đếm +1 và xóa đảo đó.

Độ phức tạp

• Thời gian: O(R × C) - mỗi ô được thăm tối đa hằng số lần.
• Không gian: O(R × C) cho call stack DFS (có thể dùng stack explicit để tránh recursion limit).

Lưu ý

Hàm mark sửa đổi trực tiếp mat1 và mat2. Nếu cần giữ nguyên, hãy deepcopy trước.