পাইথনের উপরের বাম বিন্দু থেকে নীচের ডান বিন্দুতে আমরা কতগুলি উপায়ে পৌঁছতে পারি তা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি N x M বাইনারি ম্যাট্রিক্স আছে। যেখানে 0 মানে খালি সেল এবং 1 মানে ব্লক করা সেল। এখন উপরের বাম কোণ থেকে শুরু করে, নীচের ডান কোণে পৌঁছানোর উপায়গুলির সংখ্যা খুঁজে বের করতে হবে। উত্তরটি খুব বড় হলে, এটিকে 10^9 + 7 দ্বারা মোড করুন।

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

0	0	1
0	0	0
1	1	0

তাহলে আউটপুট হবে 2, কারণ নীচে ডানদিকে যাওয়ার দুটি উপায় আছে:[ডান, ডাউন, রাইট, ডাউন] এবং [ডাউন, রাইট, রাইট, ডাউন]।

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

dp :=প্রদত্ত ম্যাট্রিক্সের একই আকারের একটি ম্যাট্রিক্স এবং 0 দিয়ে পূরণ করুন
dp[0, 0] :=1
আমি রেঞ্জ 1 থেকে ম্যাট্রিক্সের সারি গণনার জন্য, কর
- যদি ম্যাট্রিক্স[i, 0] 1 এর মত হয়, তাহলে
  - লুপ থেকে বেরিয়ে আসুন
- অন্যথায়,
  - dp[i, 0] :=1
j এর জন্য রেঞ্জ 1 থেকে ম্যাট্রিক্সের কলাম কাউন্ট, করুন
- যদি ম্যাট্রিক্স[0, j] 1 এর মত হয়, তাহলে
  - লুপ থেকে বেরিয়ে আসুন
- অন্যথায়,
  - dp[0, j] :=1
আমি রেঞ্জ 1 থেকে ম্যাট্রিক্সের সারি গণনার জন্য, কর
- j এর জন্য রেঞ্জ 1 থেকে ম্যাট্রিক্সের কলাম কাউন্ট, করুন
  - যদি ম্যাট্রিক্স[i, j] 1 এর মত হয়, তাহলে
    - dp[i, j] :=0
  - অন্যথায়,
    - dp[i, j] :=dp[i - 1, j] + dp[i, j - 1]
dp এর নিচের ডানদিকের মান ফেরত দিন

উদাহরণ (পাইথন)

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

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

ইনপুট

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]