在Python中检查我们可以选择矩阵的空单元格的数量

假设我们有一个N x N二进制矩阵，其中0表示空单元格，1表示堵塞的单元格，我们必须找到选择N个空单元格的方法，使每个行和每个列都至少有一个选定单元格。如果答案非常大，请将结果返回模10^9 + 7的余数

因此，如果输入如下所示

那么输出将为4，因为我们有以下配置（其中x是所选的单元格）−

为了解决这个问题，我们将按照以下步骤进行 –

• n：矩阵的大小
• 定义一个函数f（）。这将取i、bs
• 如果i >= n，则
  • 返回1
• ans：= 0
• for j in range 0 to n, do
  • 如果矩阵[i，j]与0相同且（2 ^ j AND bs与0相同），则
    • ans：= ans + f（i + 1，bs OR 2 ^ j）
• return ans
• 从主方法调用并返回f（0，0）

让我们看下面的实现，以更好地理解 −

例子

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))

输入

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

输出

4