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

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

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

1	1	0
1	0	1
1	1	1

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

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

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