Chương trình đếm số phép lật cột tối thiểu để biến ma trận thành ma trận đích trong Python

Cho ma trận M và ma trận đích T cùng kích thước. Phép toán: lật một cột (0->1, 1->0). Có thể sắp xếp lại hàng miễn phí. Tìm số phép lật tối thiểu để biến M thành T, trả về -1 nếu không thể.

Ví dụ

Đầu vào: ma trận M, T (xem code).
Đầu ra: 1.

Thuật toán

1. Chuyển mỗi hàng thành số nguyên nhị phân (bit thấp là cột cuối).
2. Với mỗi hàng của M làm hàng tham chiếu, tính my_xor = row_M ^ row_T[0].
3. Kiểm tra xem có thể ghép các hàng còn lại của M với các hàng của T bằng cách XOR với my_xor (sử dụng Counter).
4. Nếu có, cập nhật kết quả = min(kết quả, số bit 1 của my_xor).
5. Trả về kết quả hoặc -1.

Mã nguồn Python

class Solution:
    def solve(self, matrix, target):
        nums1 = []
        nums2 = []
        for row in matrix:
            ths = 0
            while row:
                ths = (ths << 1) + row.pop()
            nums1.append(ths)
        for row in target:
            ths = 0
            while row:
                ths = (ths << 1) + row.pop()
            nums2.append(ths)
        ret = float('inf')
        from collections import Counter
        for num in nums1:
            cts = Counter(nums1)
            cts[num] -= 1
            my_xor = num ^ nums2[0]
            for i in range(1, len(nums2)):
                needed = my_xor ^ nums2[i]
                if not cts[needed]:
                    break
                cts[needed] -= 1
            else:
                ret = min(ret, bin(my_xor).count('1'))
        return ret if ret != float('inf') else -1

ob = Solution()
M = [[0,0],[1,0],[1,1]]
T = [[0,1],[1,0],[1,1]]
print(ob.solve(M, T))

Đầu vào / Đầu ra

Input: M = [[0,0],[1,0],[1,1]], T = [[0,1],[1,0],[1,1]]
Output: 1