Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Python

Chương trình đếm số cách chọn ô trống trong ma trận Python

Cho ma trận nhị phân N×N: 0 = ô trống, 1 = ô chặn. Tìm số cách chọn N ô trống sao cho mỗi hàng và mỗi cột có ít nhất 1 ô được chọn. Kết quả modulo 109+7.

Ví dụ ma trận 3×3 với 1 ô chặn tại (2,1) → output 4.

Thuật toán Backtracking + Bitmask:

  • Duyệt hàng từ 0 đến N-1
  • Trạng thái: bs (bitmask) các cột đã chọn
  • Tại hàng i, thử mọi cột j:
    • Nếu matrix[i][j] == 0 và cột j chưa dùng ((1<)
    • Đệ quy f(i+1, bs | (1<
  • Base case: i >= N → return 1 (tìm được 1 cách hợp lệ)

Triển khai

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        
        def f(i, bs):
            if i >= n:
                return 1
            ans = 0
            for j in range(n):
                if matrix[i][j] == 0 and ((1 << j) & bs == 0):
                    ans += f(i + 1, bs | (1 << j))
            return ans
        
        return f(0, 0)

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

Đầu vào

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

Đầu ra

4

Giải thích: Đây là bài toán đếm số perfect matching trong bipartite graph (hàng - cột), cạnh tồn tại nếu ô = 0. Bitmask bs theo dõi cột đã dùng. Phức tạp O(N!) worst case, nhưng N thường nhỏ (≤15-20). Có thể tối ưu bằng DP + bitmask (Held-Karp) O(N×2^N) hoặc dùng thuật toán Hungarian cho counting (phức tạp).

Lưu ý: Code gốc thiếu modulo 109+7. Cần thêm ans %= MOD trong đệ quy.