পাইথনে আমরা কত উপায়ে ম্যাট্রিক্সকে k টুকরোতে কাটতে পারি তা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স এবং আরেকটি মান k আছে। আপনি ম্যাট্রিক্সটিকে k টুকরোগুলিতে বিভক্ত করতে চান যাতে প্রতিটি অংশে কমপক্ষে একটি 1 থাকে। তবে কাটার জন্য কিছু নিয়ম আছে, আমাদের ক্রমানুসারে অনুসরণ করতে হবে:1. একটি দিক নির্বাচন করুন:উল্লম্ব বা অনুভূমিক 2. দুটি বিভাগে কাটার জন্য ম্যাট্রিক্সে একটি সূচক নির্বাচন করুন। 3. যদি আমরা উল্লম্বভাবে কাটা, আমরা আর বাম অংশ কাটতে পারি না কিন্তু শুধুমাত্র ডান অংশ কাটা চালিয়ে যেতে পারি। 4. আমরা অনুভূমিকভাবে কাটা হলে, আমরা আর উপরের অংশটি কাটতে পারি না এবং কেবল নীচের অংশটি কাটা চালিয়ে যেতে পারি। তাই ম্যাট্রিক্সকে ভাগ করার জন্য আমাদেরকে বিভিন্ন উপায়ের সংখ্যা খুঁজে বের করতে হবে। উত্তরটি খুব বড় হলে, ফলাফল মোড (10^9 + 7) ফেরত দিন।

সুতরাং, যদি ইনপুট মত হয়

k =2, তাহলে আউটপুট হবে 4, কারণ আমরা উল্লম্বভাবে দুইবার এবং অনুভূমিকভাবে দুইবার কাটতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• p :=10^9 + 7
• m :=ম্যাট্রিক্সের সারি গণনা, n :=ম্যাট্রিক্সের কলাম গণনা
• গণনা :=একটি খালি মানচিত্র
• m - 1 থেকে 0 রেঞ্জের জন্য,
  করুন n - 1 থেকে 0 পর্যন্ত j-এর জন্য
  • করুন
    • গণনা[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 রেঞ্জের জন্য, কর
  • যদি 0 <গণনা করে[(i, y)] <গণনা করে, তাহলে
    • উত্তর :=ans + f(i, y, c - 1)
y + 1 থেকে n - 1 রেঞ্জে j-এর জন্য
• করুন
  • যদি 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

আউটপুট

4