পাইথনের একটি প্রদত্ত ম্যাট্রিক্স থেকে আমরা সর্বাধিক পরিমাণ মুদ্রা সংগ্রহ করতে পারি তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি 2D ম্যাট্রিক্স আছে যেখানে ম্যাট্রিক্স [r, c] সেই ঘরে কয়েনের সংখ্যাকে প্রতিনিধিত্ব করে। আমরা যেকোনো অবস্থান থেকে শুরু করতে পারি এবং চারটি দিক (উপর, নিচে, বাম এবং ডানদিকে, তির্যকভাবে নয়) যে কোনো একটি সরানোর মাধ্যমে মুদ্রা সংগ্রহ করতে চাই। যখন আমরা একটি কক্ষে যাই তখন কয়েনগুলি সংগ্রহ করা হয় এবং সেই ঘরের মান 0 হয়ে যায়৷ আমরা 0টি কয়েন সহ একটি কক্ষ পরিদর্শন করতে পারি না, আমাদের সর্বোচ্চ পরিমাণ কয়েন সংগ্রহ করতে হবে৷

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

তাহলে আউটপুট হবে 18, কারণ আমরা 2 −> 3 −> 6 −> 4 −> 3

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

• যদি ম্যাট্রিক্স খালি হয়, তাহলে

  • ফেরত 0

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

• x :=একটি তালিকা যেমন [−1, 1, 0, 0], y :=একটি তালিকা যেমন [0, 0, −1, 1]

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

  লাগবে৷

• ret :=0

• k এর জন্য 0 থেকে 3 রেঞ্জে, করুন

  • (t1, t2) :=(x[k] + a, y[k] + b)

  • যদি (t1, t2) বৈধ ঘর হয়, তাহলে

    • t :=mat[t1, t2], mat[t1, t2] :=0

    • ret :=ret এর সর্বোচ্চ এবং (util(t1, t2) + t)

    • mat[t1, t2] :=t

• রিটার্ন রিটার্ন

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

• res :=0

• 0 থেকে n − 1 রেঞ্জের i জন্য, করুন

  • 0 থেকে m − 1 রেঞ্জে j-এর জন্য করুন

    • যদি mat[i, j] অ-শূন্য হয়, তাহলে

      • t :=mat[i, j], mat[i, j] :=0

      • res :=res এর সর্বোচ্চ এবং (util(i, j) + temp)

• রিটার্ন রিটার্ন

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

উদাহরণ

class Solution:
   def solve(self, mat):
      if not mat:
         return 0
      n, m = len(mat), len(mat[0])
      x, y = [−1, 1, 0, 0], [0, 0, −1, 1]
      def ok(a, b):
         return 0 <= a < n and 0 <= b < m and mat[a][b]
      def util(a, b):
         ret = 0
         for k in range(4):
            t1, t2 = x[k] + a, y[k] + b
            if ok(t1, t2):
               t, mat[t1][t2] = mat[t1][t2], 0
               ret = max(ret, util(t1, t2) + t)
               mat[t1][t2] = t
            return ret
         res = 0
         for i in range(n):
            for j in range(m):
               if mat[i][j]:
                  temp, mat[i][j] = mat[i][j], 0
                  res = max(res, util(i, j) + temp)
         return res
ob = Solution()
matrix = [
   [2, 4, 3],
   [3, 6, 0],
   [2, 0, 12]
]
print(ob.solve(matrix))

ইনপুট

[
[2, 4, 3],
[3, 6, 0],
[2, 0, 12] ]

আউটপুট

18