Bài toán: Cho hai ma trận mat1, mat2 cùng kích thước N×M. Cho phép chuyển vị (transpose) bất kỳ ma trận con vuông nào của mat1. Kiểm tra có thể biến mat1 thành mat2 không.
Quan sát quan trọng
Chuyển vị ma trận con vuông chỉ hoán đổi các phần tử trên cùng một đường chéo anti-diagonal (chéo phụ). Các phần tử trên cùng một anti-diagonal (i+j = const) có thể hoán vị tùy ý với nhau.
→ Điều kiện cần và đủ: Với mọi anti-diagonal, multiset các phần tử của mat1 và mat2 phải giống nhau.
Triển khai Python
def solve(mat1, mat2):
row, col = len(mat1), len(mat1[0])
# Kiểm tra các anti-diagonal bắt đầu từ cột 0
for i in range(row):
temp1, temp2 = [], []
r, c = i, 0
while r >= 0 and c < col:
temp1.append(mat1[r][c])
temp2.append(mat2[r][c])
r -= 1
c += 1
if sorted(temp1) != sorted(temp2):
return False
# Kiểm tra các anti-diagonal bắt đầu từ hàng cuối
for j in range(1, col):
temp1, temp2 = [], []
r, c = row - 1, j
while r >= 0 and c < col:
temp1.append(mat1[r][c])
temp2.append(mat2[r][c])
r -= 1
c += 1
if sorted(temp1) != sorted(temp2):
return False
return True
# Test
mat1 = [[5,6,7], [1,2,3], [6,8,9]]
mat2 = [[5,6,2], [1,7,3], [6,8,9]]
print(solve(mat1, mat2)) # True: transpose top-right 2x2 submatrix
Kết quả
True
Giải thích
- Duyệt tất cả anti-diagonal (i+j = const): từ cột 0 các hàng, rồi từ hàng cuối các cột.
- Thu thập phần tử trên mỗi anti-diagonal của hai ma trận, sort và so sánh.
- Nếu mọi anti-diagonal đều khớp multiset → có thể biến đổi được.
- Độ phức tạp: O(NM log(min(N,M))) do sort mỗi diagonal.