Bài toán: Cho 2 ma trận mat1, mat2 cùng kích thước. Cho phép swap mat1[i][j] với mat2[i][j] (cùng vị trí). Kiểm tra có thể làm cho CẢ HAI ma trận đều tăng chặt theo hàng và cột không.
Thuật toán Greedy
Tại mỗi vị trí (i,j), đặt giá trị nhỏ hơn vào mat1, lớn hơn vào mat2. Sau đó kiểm tra cả hai có tăng chặt không.
Triển khai Python
def solve(mat1, mat2):
row, col = len(mat1), len(mat1[0])
# Bước 1: Đảm bảo mat1[i][j] <= mat2[i][j] tại mọi vị trí
for i in range(row):
for j in range(col):
if mat1[i][j] > mat2[i][j]:
mat1[i][j], mat2[i][j] = mat2[i][j], mat1[i][j]
# Bước 2: Kiểm tra tăng chặt theo hàng
for i in range(row):
for j in range(col - 1):
if mat1[i][j] >= mat1[i][j + 1] or mat2[i][j] >= mat2[i][j + 1]:
return False
# Bước 3: Kiểm tra tăng chặt theo cột
for i in range(row - 1):
for j in range(col):
if mat1[i][j] >= mat1[i + 1][j] or mat2[i][j] >= mat2[i + 1][j]:
return False
return True
# Test
mat1 = [[7, 15], [16, 10]]
mat2 = [[14, 9], [8, 17]]
print(solve(mat1, mat2)) # True
# Sau swap: mat1=[[7,9],[8,10]], mat2=[[14,15],[16,17]] - cả hai đều tăng chặt
Kết quả
True
Giải thích
- Greedy: tại mỗi ô, đặt min vào mat1, max vào mat2. Đây là lựa chọn tối ưu cục bộ dẫn đến tối ưu toàn cục.
- Sau khi chuẩn hóa, kiểm tra điều kiện tăng chặt:
mat[i][j] < mat[i][j+1](hàng) vàmat[i][j] < mat[i+1][j](cột). - Nếu vi phạm bất kỳ đâu → False.
- Độ phức tạp: O(NM) time, O(1) extra space (sửa in-place).