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

Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम


मान लीजिए हमारे पास एक N x N बाइनरी मैट्रिक्स है जहां 0 खाली सेल के लिए है और 1 ब्लॉक्ड सेल है, हमें N खाली सेल चुनने के तरीकों की संख्या ढूंढनी है ताकि हर पंक्ति और हर कॉलम में कम से कम एक चुना हुआ सेल हो। यदि उत्तर बहुत बड़ा है तो परिणाम mod 10^9 + 7 लौटाएं

इसलिए, यदि इनपुट इस तरह है

000
000
010

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

Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम

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

  • 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
  1. पायथन प्रोग्राम: जांचें कि स्ट्रिंग खाली है या नहीं पायथन प्रोग्राम: जांचें कि स्ट्रिंग खाली है या नहीं

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट एक स्ट्रिंग इनपुट दिए जाने पर, हमें जांचना होगा कि स्ट्रिंग खाली है या नहीं। पायथन स्ट्रिंग्स प्रकृति में इम्यूटेबल होती हैं इसलिए किसी भी ऑपरेशन को करते समय स्ट्रिंग्स को संभालते समय

  1. पायथन प्रोग्राम में कैसे जांचें कि दी गई संख्या फाइबोनैचि नंबर है या नहीं? पायथन प्रोग्राम में कैसे जांचें कि दी गई संख्या फाइबोनैचि नंबर है या नहीं?

    इस लेख में, हम नीचे दिए गए प्रॉब्लम स्टेटमेंट के समाधान के बारे में सीखेंगे: प्रॉब्लम स्टेटमेंट एक संख्या n दिए जाने पर, जांचें कि n फाइबोनैचि नंबर है या नहीं। हम सभी जानते हैं कि nth फाइबोनैचि नंबर पिछले दो फाइबोनैचि नंबर्स का योग होता है। लेकिन वे पुनरावृत्ति संबंध के अलावा एक दिलचस्प संबंध भी प

  1. पायथन प्रोग्राम: जांचें कि दी गई संख्या फाइबोनैचि संख्या है या नहीं पायथन प्रोग्राम: जांचें कि दी गई संख्या फाइबोनैचि संख्या है या नहीं

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे -समस्या कथनएक संख्या n दी गई है, जांचें कि क्या n एक फाइबोनैचि संख्या है या नहींहम सभी जानते हैं कि nth फाइबोनैचि संख्या पिछली दो फाइबोनैचि संख्याओं का योग है। लेकिन वे पुनरावृत्ति संबंध के अलावा एक दिलचस्प संबंध भी प्रदान करते हैं।