यह जांचने के लिए कार्यक्रम कि हम कितने तरीकों से अजगर में एक मैट्रिक्स की खाली कोशिकाओं को चुन सकते हैं

मान लीजिए कि हमारे पास एक एन एक्स एन बाइनरी मैट्रिक्स है जहां 0 खाली कोशिकाओं के लिए है और 1 एक अवरुद्ध सेल है, हमें एन खाली कोशिकाओं को चुनने के तरीकों की संख्या का पता लगाना होगा जैसे कि प्रत्येक पंक्ति और प्रत्येक कॉलम में कम से कम एक चुना हुआ सेल हो। यदि उत्तर बहुत बड़ा है तो वापसी परिणाम मॉड 10^9 + 7

तो, अगर इनपुट पसंद है

तो आउटपुट 4 होगा, क्योंकि हमारे पास निम्नलिखित कॉन्फ़िगरेशन हैं (जहां x एक चयनित सेल है) -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=मैट्रिक्स का आकार
• फ़ंक्शन f() को परिभाषित करें। यह मैं, बीएस ले जाएगा
• अगर मैं>=n, तो
  • वापसी 1
• उत्तर:=0
• जे के लिए 0 से n की सीमा में, करें
  • यदि मैट्रिक्स [i, j] 0 के समान है और (2^j और bs 0 के समान है), तो
    • Ans :=ans + f(i + 1, bs OR 2^j)
• वापसी उत्तर
• मुख्य विधि से कॉल करें और 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