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

ধরি আমাদের একটি বাইনারি ম্যাট্রিক্স এবং আরেকটি মান k আছে। আপনি ম্যাট্রিক্সকে k টুকরোতে ভাগ করতে চান যাতে প্রতিটি টুকরোতে কমপক্ষে একটি ১ থাকে। কিন্তু কাটার কিছু নিয়ম মানতে হবে ক্রমশः: ১. দিক নির্বাচন: ভার্টিক্যাল বা হরিজন্টাল ২. ম্যাট্রিক্সে একটি ইনডেক্স নির্বাচন করুন যেটি দুটি সেকশনে কাটবে। ৩. যদি ভার্টিক্যালি কাটেন, তবে বাম অংশ আর কাটা যাবে না, শুধু ডান অংশ কাটা চালাতে পারবেন। ৪. যদি হরিজন্টালি কাটেন, তবে উপরের অংশ আর কাটা যাবে না, শুধু নিচের অংশ কাটা চালাতে পারবেন। আমাদের ম্যাট্রিক্স ভাগ করার ভিন্ন ভিন্ন উপায়ের সংখ্যা বের করতে হবে। যদি উত্তর খুব বড় হয়, তবে রেজাল্ট মড (১০^৯ + ৭) রিটার্ন করুন।

তাই, ইনপুট যদি নিচের ম্যাট্রিক্স এবং k = 2 হয়, তবে আউটপুট হবে ৪, কারণ আমরা দুবার ভার্টিক্যালি এবং দুবার হরিজন্টালি কাটতে পারি।

সমাধানের ধাপগুলো:

• p := 10^9 + 7
• m := ম্যাট্রিক্সের সারি সংখ্যা, n := কলাম সংখ্যা
• counts := একটি খালি ম্যাপ
• i = m-1 থেকে ০ পর্যন্ত, করুন
  • j = n-1 থেকে ০ পর্যন্ত, করুন
    • 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 ০ এর সমান হয়, তবে
  • count > 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

আউটপুট

4