Chuyển đổi ma trận nhị phân bằng đảo bit góc ma trận con (Python)

Bài toán: Cho hai ma trận nhị phân A, B kích thước N×M. Cho phép chọn ma trận con ≥2×2 và flip (XOR 1) 4 góc. Kiểm tra có thể biến A thành B không.

Quan sát

Thao tác flip 4 góc của ma trận con (i,j), (i,k), (l,j), (l,k) tương đương với: flip (i,j) cùng lúc với 3 góc gốc (0,0), (0,k), (l,0).
→ Có thể giảm bài toán về: chỉ được flip (i,j) cùng với (0,0), (0,j), (i,0).

Thuật toán greedy

Duyệt từ (1,1) đến (N-1,M-1). Nếu A[i][j] != B[i][j], thực hiện flip 4 góc: (0,0), (0,j), (i,0), (i,j). Cuối cùng kiểm tra toàn bộ ma trận.

Triển khai Python

def solve(mat1, mat2):
    row, col = len(mat1), len(mat1[0])
    
    for i in range(1, row):
        for j in range(1, col):
            if mat1[i][j] != mat2[i][j]:
                mat1[i][j] ^= 1
                mat1[0][0] ^= 1
                mat1[0][j] ^= 1
                mat1[i][0] ^= 1
    
    for i in range(row):
        for j in range(col):
            if mat1[i][j] != mat2[i][j]:
                return False
    return True

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

Kết quả

True

Giải thích

• Greedy: sửa từng ô (i,j) từ trên trái sang dưới phải bằng cách flip ma trận con (0,0)-(i,j).
• Sau khi duyệt xong, chỉ còn lại hàng 0 và cột 0 có thể khác. Kiểm tra toàn bộ.
• Độ phức tạp: O(NM).
• Lưu ý: hàm sửa đổi mat1 in-place.