কয়েনের সংখ্যা খুঁজে বের করার প্রোগ্রাম আমরা উপরের বাম থেকে নীচে-ডান ঘরে বাছাই করতে পারি এবং পাইথনে ফিরে আসতে পারি

ধরুন আমাদের কাছে 3টি সম্ভাব্য মান সহ একটি 2D ম্যাট্রিক্স আছে −

• একটি খালি ঘরের জন্য 0৷

  ৷

• একটি মুদ্রার জন্য 1।

• −1 দেয়ালের জন্য।

উপরের-বাম কক্ষ থেকে শুরু করে এবং শুধুমাত্র ডান বা নীচের দিকে সরে গিয়ে নীচের ডান কক্ষে পৌঁছানোর মাধ্যমে আমাদের সর্বোচ্চ সংখ্যক কয়েন খুঁজে বের করতে হবে। তারপর শুধুমাত্র উপরে বা বাম দিকে সরে উপরের বাম কক্ষে ফিরে আসুন। যখন আমরা একটি মুদ্রা বাছাই করি, তখন ঘরের মান 0 হয়ে যায়। যদি আমরা নীচের ডান ঘরে পৌঁছাতে না পারি, তাহলে 0 ফেরত দিন।

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

তাহলে আউটপুট হবে 8.

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

• n :=ম্যাটের সারি গণনা, m :=ম্যাটের কলাম গণনা

• একটি ফাংশন util() সংজ্ঞায়িত করুন। এর জন্য i, j, k, l

  লাগবে

• যদি i এবং j ম্যাটের পরিসরে না হয় বা ম্যাট[i, j] −1 এর মত হয়, তাহলে

  • রিটার্ন −inf

• যদি k এবং l মাদুরের পরিসরে না হয় বা ম্যাট[k, l] −1 এর মত হয়, তাহলে

  • রিটার্ন −inf

• যদি i, j, k এবং l সব 0 হয়, তাহলে

  • রিটার্ন ম্যাট[0, 0]

• সেরা :=−inf

• প্রতিটি জোড়ার জন্য (dx1, dy1) [(−1, 0) ,(0, −1) ], করুন

  • প্রতিটি জোড়ার জন্য (dx2, dy2) [(−1, 0) ,(0, −1) ], করুন

    • সর্বোত্তম :=সর্বোত্তম এবং উপযোগের সর্বোচ্চ (i + dy1, j + dx1, k + dy2, l + dx2)

• রিটার্ন ম্যাট[i, j] +(1 যখন i k এর মতো নয়, অন্যথায় 0) * mat[k, l] + সেরা

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• সর্বোচ্চ 0 ফেরত দিন এবং util(n − 1, m − 1, n − 1, m − 1)

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

উদাহরণ

class Solution:
   def solve(self, mat):
      n, m = len(mat), len(mat[0])
      def util(i, j, k, l):
         if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
            return −1e9
         if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
            return −1e9
         if i == 0 and j == 0 and k == 0 and l == 0:
            return mat[0][0]
         best = −1e9
         for dx1, dy1 in [(−1, 0), (0, −1)]:
            for dx2, dy2 in [(−1, 0), (0, −1)]:
               best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
         return mat[i][j] + (i != k) * mat[k][l] + best
      return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]
print(ob.solve(matrix))

ইনপুট

[
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]

আউটপুট

8