ตรวจสอบว่า Matrix A แปลงเป็น B ได้โดยเปลี่ยน Parity มุม Submatrix หรือไม่ด้วย Python

สมมติมี Binary Matrix A และ B ขนาด N x M Operation: เลือก Sub-matrix (อย่างน้อย 2x2) แล้ว Flip Bit ที่ 4 มุม ต้องตรวจสอบว่า A -> B ได้หรือไม่

เช่น A = [[1,0,0],[1,0,1],[1,0,0]] B = [[0,1,0],[0,1,1],[1,0,0]] Output True (Flip Top-left 2x2)

ขั้นตอนแก้ (Greedy):

• วน i=1..row-1, j=1..col-1: ถ้า A[i][j] != B[i][j] ให้ Flip A[i][j], A[0][0], A[0][j], A[i][0]
• หลังจบ ตรวจสอบว่า A == B ทุก Element

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

def solve(mat1, mat2):
    row = len(mat1)
    column = len(mat1[0])
    for i in range(1, row):
        for j in range(1, column):
            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(column):
            if mat1[i][j] != mat2[i][j]:
                return False
    return True

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

Input

[[1, 0, 0], [1, 0, 1], [1, 0, 0]], [[0, 1, 0], [0, 1, 1], [1, 0, 0]]

Output

True