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

ধরুন আমাদের একটি ম্যাট্রিক্স আছে; আমাদের দীর্ঘতম ক্রমবর্ধমান পথের দৈর্ঘ্য খুঁজে বের করতে হবে। প্রতিটি কোষ থেকে, আমরা হয় চারটি দিকে যেতে পারি - বাম, ডান, উপরে বা নীচে। আমরা তির্যকভাবে সরতে পারি না বা সীমানার বাইরে যেতে পারি না।

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

তাহলে আউটপুট হবে 4 কারণ দীর্ঘতম ক্রমবর্ধমান পথ হল [3, 4, 5, 6]।

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

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

  লাগবে

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

  • dp[i, j]

    ফেরত দিন

• dp[i, j] :=1

• তাপমাত্রা :=0

• i-1 থেকে i+2 রেঞ্জের জন্য, করুন

  • j-1 থেকে j+2 পরিসরে c এর জন্য, করুন

    • যদি r i এর মত হয় এবং c j এর মত হয় অথবা(|r-i| 1 এর মত এবং |c-j| 1 এর মত হয়) তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • যদি c>=0 এবং r>=0 এবং r<ম্যাট্রিক্সের সারি গণনা এবং c <ম্যাট্রিক্সের আকার [0] এবং ম্যাট্রিক্স[r, c]>ম্যাট্রিক্স[i, j], তাহলে

      • temp :=তাপমাত্রার সর্বোচ্চ, সমাধান(r, c, matrix)

• dp[i, j] :=dp[i, j] + temp

• dp[i, j]

  ফেরত দিন

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

• যদি ম্যাট্রিক্স অ-শূন্য হয়, তাহলে

  • রিটার্ন 0

• dp :=প্রদত্ত ম্যাট্রিক্সের মতো আকারের একটি ম্যাট্রিক্স এবং 0

  দিয়ে পূরণ করুন

• উত্তর :=0

• আমি 0 থেকে ম্যাট্রিক্সের আকারের মধ্যে, কর

  • j এর জন্য রেঞ্জ 0 থেকে ম্যাট্রিক্সের আকার[0], করুন

    • যদি dp[i, j] 0 এর মত হয়, তাহলে

      • সমাধান (i, j, matrix)

• উত্তর ফেরত দিন

উদাহরণ

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

class Solution(object):
   def solve(self,i,j,matrix):
      if self.dp[i][j]:
         return self.dp[i][j]
      self.dp[i][j] = 1
      temp = 0
      for r in range(i-1,i+2):
         for c in range(j-1,j+2):
            if r==i and c==j or (abs(r-i)==1 and abs(c-j)==1):
               continue
            if c>=0 and r>=0 and r<len(matrix) and c<len(matrix[0]) and matrix[r][c]>matrix[i][j]:
temp = max(temp,self.solve(r,c,matrix))
               self.dp[i][j]+=temp
               return self.dp[i][j]
   def longestIncreasingPath(self, matrix):
      if not matrix:
         return 0
      self.dp = [ [0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
      self.ans = 0
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if self.dp[i][j]==0:
               self.solve(i,j,matrix)
            self.ans = max(self.ans,self.dp[i][j])
      return self.ans

ob = Solution()
print(ob.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))

ইনপুট

[[9,9,4],[6,6,8],[2,1,1]]

আউটপুট

4