Python में मैट्रिक्स को k टुकड़ों में काटने के कितने तरीके हैं, इसकी गिनती करने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स और एक अन्य मान k है। आप मैट्रिक्स को k टुकड़ों में विभाजित करना चाहते हैं ताकि प्रत्येक टुकड़े में कम से कम एक 1 हो। लेकिन काटने के लिए कुछ नियम हैं, जिनका हमें क्रम में पालन करना होगा: 1. एक दिशा चुनें: लंबवत या क्षैतिज 2. मैट्रिक्स में एक इंडेक्स चुनें जिसे दो खंडों में काटा जाए। 3. यदि हम लंबवत काटते हैं, तो हम बाएं हिस्से को अब और नहीं काट सकते लेकिन केवल दाएं हिस्से को काटना जारी रख सकते हैं। 4. यदि हम क्षैतिज काटते हैं, तो हम ऊपरी हिस्से को अब और नहीं काट सकते और केवल निचले हिस्से को काटना जारी रख सकते हैं। इसलिए हमें मैट्रिक्स को विभाजित करने के विभिन्न तरीकों की संख्या ढूंढनी है। यदि उत्तर बहुत बड़ा है, तो परिणाम mod (10^9 + 7) लौटाएं।

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

1	1	0
1	0	1
1	1	1

k = 2, तो आउटपुट 4 होगा, क्योंकि हम दो बार लंबवत और दो बार क्षैतिज काट सकते हैं।

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

p := 10^9 + 7
m := मैट्रिक्स की पंक्ति संख्या, n := मैट्रिक्स की कॉलम संख्या
counts := एक खाली मैप
i के लिए m-1 से 0 तक रेंज में, करें
- j के लिए n-1 से 0 तक रेंज में, करें
  - counts[i, j] := counts[i + 1, j] + counts[(i, j + 1)] - counts[(i + 1, j + 1)] + matrix[i, j]
f() फ़ंक्शन परिभाषित करें। यह x, y, c लेगा
count := counts[x, y]
यदि c 0 के समान है, तो
- count > 0 होने पर 1 लौटाएं अन्यथा 0
ans := 0
i के लिए x+1 से m-1 तक रेंज में, करें
- यदि 0 < counts[(i, y)] < count, तो
  - ans := ans + f(i, y, c - 1)
j के लिए y+1 से n-1 तक रेंज में, करें
- यदि 0 < counts[(x, j)] < count, तो
  - ans := ans + f(x, j, c - 1)
ans mod p लौटाएं
मुख्य मेथड से f(0, 0, k - 1) को कॉल करें और लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

from collections import defaultdict
class Solution:
    def solve(self, matrix, k):
        p = 10 ** 9 + 7
        m, n = len(matrix), len(matrix[0])
        counts = defaultdict(int)
        for i in range(m)[::-1]:
            for j in range(n)[::-1]:
                counts[(i, j)] = (counts[(i + 1, j)] + counts[(i, j + 1)] - counts[(i + 1, j + 1)] + matrix[i][j])
        def f(x, y, c):
            count = counts[(x, y)]
            if c == 0:
                return 1 if count > 0 else 0
            ans = 0
            for i in range(x + 1, m):
                if 0 < counts[(i, y)] < count:
                    ans += f(i, y, c - 1)
            for j in range(y + 1, n):
                if 0 < counts[(x, j)] < count:
                    ans += f(x, j, c - 1)
            return ans % p
        return f(0, 0, k - 1)
ob = Solution()
matrix = [
    [1, 1, 0],
    [1, 0, 1],
    [1, 1, 1],
]
k = 2
print(ob.solve(matrix, k))

इनपुट

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