পাইথনে শুরু থেকে শেষ বিন্দু পর্যন্ত k খরচ সহ পাথের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি 2d বাইনারি ম্যাট্রিক্স এবং আরেকটি মান k আছে। এখন উপরের-বাম ঘর থেকে শুরু করে নীচের ডানদিকের ঘরে যেতে হবে। এক ধাপে, আমরা কেবল নীচে যেতে পারি, বা ডানদিকে যেতে পারি। এখন একটি পথের স্কোর হল পাথের কক্ষের মানের সমষ্টি। স্কোর k দিয়ে স্টার্ট সেল থেকে শেষ সেল পর্যন্ত পাথের সংখ্যা বের করতে হবে। যদি বিশাল সম্ভাব্য উপায় থাকে তাহলে ফলাফল মোড 10^9+7 ফেরত দিন।

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

৷ ৷ ৷

0	0	1
1	0	1
0	1	0

K =2, তাহলে আউটপুট হবে 4, কারণ স্কোর 2 সহ পাথগুলি হল [R,R,D,D], [D,R,R,D], [D,D,R,R], [D ,R,D,R] এখানে D নিচে এবং R ডান।

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

deno :=10^9 + 7
m :=ম্যাট্রিক্সের সারি গণনা, n :=ম্যাট্রিক্সের কলাম গণনা
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি i, j, pts
লাগবে
যদি i>=m বা j>=n, তাহলে
- ফেরত 0
pts :=pts + ম্যাট্রিক্স[i, j]
যদি i m - 1 এর মত হয় এবং j n - 1 এর মত হয়, তাহলে
- 1 ফেরত দিন যখন pts k এর মত হয় অন্যথায় 0
রিটার্ন dfs(i + 1, j, pts) + dfs(i, j + 1, pts)
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
রিটার্ন dfs(0, 0, 0) mod deno

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, matrix, k):
      m, n = len(matrix), len(matrix[0])
      def dfs(i=0, j=0, pts=0):
         if i >= m or j >= n:
            return 0
         pts += matrix[i][j]
         if i == m - 1 and j == n - 1:
            return int(pts == k)
         return dfs(i + 1, j, pts) + dfs(i, j + 1, pts)
      return dfs() % (10 ** 9 + 7)

ob = Solution()
matrix = [
   [0, 0, 1],
   [1, 0, 1],
   [0, 1, 0]
]
k = 2
print(ob.solve(matrix, k))

ইনপুট

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