Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> Python

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

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

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

0
0
0
0
0
0
0
1
0

तो आउटपुट 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

  1. Python

    पायथन में एक बाइनरी ट्री में दो नोड्स के बीच पथ का सबसे बड़ा योग खोजने का कार्यक्रम

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें किन्हीं दो नोड्स के बीच किसी भी पथ का अधिकतम योग ज्ञात करना है। तो, अगर इनपुट पसंद है तब आउटपुट 62 होगा क्योंकि नोड [12,13,14,16,7] हैं। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - एक फ़ंक्शन को परिभाषित करें utils() । यह जड़ लेगा अगर रूट अ

  1. HTML

    एचटीएमएल डोम डालने से पहले () विधि

    HTML DOM insertBefore () विधि पहले से मौजूद चाइल्ड नोड से पहले एक नया नोड सम्मिलित करती है। सिंटैक्स निम्नलिखित वाक्य रचना है - कॉलिंग इंसर्ट बिफोर () पोजीशनस्ट्रिंग और टेक्स्ट के मापदंडों के साथ node.insertBefore(newNode, existingNode) यहां, पैरामीटर निम्नलिखित हो सकते हैं - पैरामीटर पैरामीटर वि

  1. Android

    एंड्रॉइड में एक्टिविटी स्टार्टअप पर ध्यान केंद्रित करने से एडिटटेक्स्ट को कैसे रोकें?

    ऐसी कई स्थितियां हैं जहां गतिविधि शुरू होने पर हमें कीबोर्ड दृश्यता की आवश्यकता नहीं होती है। यह उदाहरण इस बारे में प्रदर्शित करता है कि एडिटटेक्स्ट को गतिविधि स्टार्टअप पर ध्यान केंद्रित करने से कैसे रोकें चरण 1 - एंड्रॉइड स्टूडियो में एक नया प्रोजेक्ट बनाएं, फाइल ⇒ न्यू प्रोजेक्ट पर जाएं और एक नय