Python程式：檢查選擇矩陣空單元格的方案數

假設我們有一個 N x N 的二進位制矩陣，其中 0 表示空單元格，1 表示被阻塞的單元格，我們需要找到選擇 N 個空單元格的方案數，使得每一行和每一列至少包含一個選中的單元格。如果答案非常大，則返回結果模 10^9 + 7。

因此，如果輸入如下所示：

0
0
0
0
0
0
0
1
0

那麼輸出將為 4，因為我們有以下配置（其中 x 是選中的單元格）：−

為了解決這個問題，我們將遵循以下步驟：−

  • n := 矩陣的大小
  • 定義一個函式 f()。它將接收 i 和 bs 作為引數。
  • 如果 i >= n，則
    • 返回 1
  • ans := 0
  • 對於 j 從 0 到 n，執行以下操作：
    • 如果 matrix[i, j] 等於 0 且 (2^j AND bs 等於 0)，則
      • ans := ans + f(i + 1, bs OR 2^j)
  • 返回 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

更新於： 2020-12-03

瀏覽量 155 次

開啟您的 職業生涯

完成課程獲得認證

開始學習
廣告