Chương trình tìm số lần hoán vị hàng tối thiểu để ma trận nhị phân có nửa trên đường chéo chính bằng 0 bằng Python

Cho ma trận nhị phân n×n. Mỗi bước hoán đổi 2 hàng liền kề. Tìm số hoán đổi tối thiểu để mọi phần tử trên đường chéo chính đều là 0. Không thể thì trả -1.

Ví dụ: [[0,1,0],[0,1,1],[1,0,0]] → 2.

Thuật toán

• n = số hàng; m[i] = vị trí 1 cuối cùng ở hàng i (tính từ phải), mặc định n
• Duyệt hàng i, tìm j từ n-1 về 0: nếu matrix[i][j]==1: m[i]=n-j-1; break
• t=0, ans=0
• Duyệt i từ 0 đến n-1:
  • t += 1
  • Tìm j từ i đến n-1: nếu m[j] >= n-t: ans += j-i; flag=True; break
  • Nếu không tìm thấy: return -1
  • Dịch m[i+1..j] = m[i..j-1] (mô phỏng hoán đổi hàng)
• Return ans

Code Python

def solve(matrix):
    n = len(matrix)
    m = [n] * n
    for i in range(n):
        for j in range(n-1, -1, -1):
            if matrix[i][j] == 1:
                m[i] = n - j - 1
                break
    t, ans = 0, 0
    for i in range(n):
        t += 1
        flag = False
        for j in range(i, n):
            if m[j] >= n - t:
                ans += j - i
                flag = True
                break
        if not flag:
            return -1
        m[i+1:j+1] = m[i:j]
    return ans

matrix = [[0,1,0],[0,1,1],[1,0,0]]
print(solve(matrix))

Input

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

Output

2