ตรวจสอบว่า Matrix หนึ่งสามารถแปลงเป็นอีก Matrix ได้โดยการ Transpose Square Sub-matrices หรือไม่ด้วย Python

สมมติมี Matrix สองตัว N x M ชื่อ mat1 และ mat2 Operation: สามารถ Transpose Square Sub-matrix ใดๆ ใน mat1 ได้ ต้องตรวจสอบว่าได้ mat2 หรือไม่

เช่น mat1 = [[5,6,7],[1,2,3],[6,8,9]] mat2 = [[5,6,2],[1,7,3],[6,8,9]] Output True เพราะ Transpose Top-right 2x2 ของ mat1 ได้ mat2

ขั้นตอนแก้:

• ตรวจสอบแต่ละ Diagonal (Anti-diagonal) ของ Matrix ทั้งสอง
• รวบรวม Element บน Diagonal เดียวกันของ mat1 และ mat2 แล้ว Sort และเปรียบเทียบ
• ถ้าทุก Diagonal ตรงกัน Return True มิฉะนั้น False

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

def solve(mat1, mat2):
    row = len(mat1)
    column = len(mat1[0])
    for i in range(row):
        temp1 = []
        temp2 = []
        r = i
        col = 0
        while r >= 0 and col < column:
            temp1.append(mat1[r][col])
            temp2.append(mat2[r][col])
            r -= 1
            col += 1
        temp1.sort()
        temp2.sort()
        for i in range(len(temp1)):
            if temp1[i] != temp2[i]:
                return False
    for j in range(1, column):
        temp1 = []
        temp2 = []
        r = row - 1
        col = j
        while r >= 0 and col < column:
            temp1.append(mat1[r][col])
            temp2.append(mat2[r][col])
            r -= 1
            col += 1
        temp1.sort()
        temp2.sort()
        for i in range(len(temp1)):
            if temp1[i] != temp2[i]:
                return False
    return True

mat1 = [[5, 6, 7], [1, 2, 3], [6, 8, 9]]
mat2 = [[5, 6, 2], [1, 7, 3], [6, 8, 9]]
print(solve(mat1, mat2))

Input

[[5, 6, 7], [1, 2, 3], [6, 8, 9]], [[5, 6, 2], [1, 7, 3], [6, 8, 9]]

Output

True