পাইথনে দীর্ঘতম ম্যাট্রিক্স পাথের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

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

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

তাহলে আউটপুট হবে 10, যেমন আমরা (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 1), (2, 0)।

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

• N :=ম্যাট্রিক্সের সারি গণনা
• M :=ম্যাট্রিক্সের কলাম সংখ্যা
• dp :=M আকারের একটি তালিকা এবং -1 দিয়ে পূরণ করুন
• আমি 0 থেকে N - 1 রেঞ্জের জন্য, কর
  • ndp :=M আকারের একটি তালিকা এবং -1 দিয়ে পূরণ করুন
  • ndp2 :=M আকারের একটি তালিকা এবং -1 দিয়ে পূরণ করুন
  0 থেকে M - 1 এর মধ্যে j-এর জন্য
  • করুন
    • যদি ম্যাট্রিক্স[i, j] 1 না হয় এবং (i একই হয় 0 বা dp[j]> -1), তাহলে
      • ndp[j] :=dp[j] + 1
      • ndp2[j] :=dp[j] + 1
  1 থেকে M - 1 এর মধ্যে j-এর জন্য
  • করুন
    • যদি ম্যাট্রিক্স[i, j] 1 না হয় এবং ndp[j - 1]> -1 হয়, তাহলে
      • ndp[j] :=সর্বাধিক ndp[j] এবং (ndp[j - 1] + 1)
  M - 2 থেকে 0 রেঞ্জের মধ্যে j-এর জন্য
  • , 1 কম করুন, করুন
    • যদি ম্যাট্রিক্স[i, j] 1 না হয় এবং ndp2[j + 1]> -1 হয়, তাহলে
      • ndp2[j] :=সর্বাধিক ndp2[j] এবং (ndp2[j + 1] + 1)
      • ndp[j] :=সর্বাধিক ndp[j] এবং ndp2[j]
  • dp :=ndp
• রিটার্ন (সর্বাধিক ডিপি) + 1

উদাহরণ

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

def solve(matrix):
   N = len(matrix)
   M = len(matrix[0])
   dp = [-1 for i in matrix[0]]
   for i in range(N):
      ndp = [-1 for j in matrix[0]]
      ndp2 = [-1 for j in matrix[0]]
      for j in range(M):
         if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
            ndp[j] = dp[j] + 1
            ndp2[j] = dp[j] + 1

      for j in range(1, M):
         if matrix[i][j] != 1 and ndp[j - 1] > -1:
            ndp[j] = max(ndp[j], ndp[j - 1] + 1)

      for j in range(M - 2, -1, -1):
         if matrix[i][j] != 1 and ndp2[j + 1] > -1:
            ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
            ndp[j] = max(ndp[j], ndp2[j])

      dp = ndp
   return max(dp) + 1

matrix = [
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print(solve(matrix))

ইনপুট

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

আউটপুট

10