পাইথনে একটি প্রদত্ত ম্যাট্রিক্সে দীর্ঘতম ক্রমবর্ধমান পথের দৈর্ঘ্যের প্রোগ্রাম

ধরুন আমাদের একটি 2D ম্যাট্রিক্স আছে, আমাদের দীর্ঘতম কঠোরভাবে ক্রমবর্ধমান পথের দৈর্ঘ্য খুঁজে বের করতে হবে। পথ অতিক্রম করার জন্য আমরা উপরে, নীচে, বাম বা ডানদিকে বা তির্যকভাবে যেতে পারি।

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

তাহলে আউটপুট হবে 6, কারণ দীর্ঘতম পথ হল [1, 2, 4, 6, 7, 9]

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

n := row count of matrix , m := column count of matrix
moves := a list of pairs to move up, down, left and right [[1, 0], [-1, 0], [0, 1], [0, -1]]
Define a function dp() . This will take y, x
if x and y are in range of matrix, then
   return 0
currVal := matrix[y, x]
res := 0
for each d in moves, do
   (dy, dx) := d
   (newY, newX) := (y + dy, x + dx)
      if newY and newX are in range of matrix and matrix[newY, newX] > currVal, then
         res := maximum of res and dp(newY, newX)
return res + 1
From the main method do the following:
result := 0
for i in range 0 to n - 1, do
   for j in range 0 to m - 1, do
      result := maximum of result and dp(i, j)
return result

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

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

class Solution:
   def solve(self, matrix):
      n, m = len(matrix), len(matrix[0])
      moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
      def dp(y, x):
         if y < 0 or y >= n or x < 0 or x >= m:
            return 0
         currVal = matrix[y][x]
         res = 0
         for d in moves:
            dy, dx = d
            newY, newX = y + dy, x + dx
            if (newY >= 0 and newY < n and newX >= 0 and newX < m and matrix[newY][newX] > currVal):
               res = max(res, dp(newY, newX))
         return res + 1
      result = 0
      for i in range(n):
         for j in range(m):
            result = max(result, dp(i, j))
      return result
ob = Solution()
matrix = [
   [2, 4, 6],
   [1, 5, 7],
   [3, 3, 9]
]
print(ob.solve(matrix))

ইনপুট

[ [2, 4, 6], [1, 5, 7], [3, 3, 9] ]

আউটপুট

6