পাইথনে গন্তব্যে পৌঁছানোর জন্য ন্যূনতম সংখ্যক উচ্চতা বাড়ানোর জন্য প্রোগ্রাম

ধরুন আমাদের একটি ম্যাট্রিক্স M আছে যেখানে M[r][c] সেই ঘরের উচ্চতাকে প্রতিনিধিত্ব করে। যদি আমরা বর্তমানে উপরের বাম কোণায় থাকি এবং নীচে ডানদিকে যেতে চাই। আমরা সংলগ্ন কক্ষে যেতে পারি (উপরে, নিচে, বামে, ডানে) তখনই যদি সেই সংলগ্ন কক্ষের উচ্চতা বর্তমান কোষের উচ্চতার চেয়ে কম বা সমান হয়। আমরা সরানোর আগে যেকোন সংখ্যক কক্ষের উচ্চতা বাড়াতে পারি, তাই আমাদের সর্বনিম্ন মোট উচ্চতা খুঁজে বের করতে হবে যা বাড়ানো দরকার যাতে আমরা নীচের ডানদিকে যেতে পারি।

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

তাহলে আউটপুট হবে 4, যেহেতু আমরা নিম্নলিখিত পথটি [2, 4, 5, 1] ​​নিতে পারি এবং এই কনফিগারেশনে উচ্চতা পরিবর্তন করতে পারি -

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

INF :=অসীম

• R, C :=ম্যাট্রিক্সের সারি সংখ্যা, ম্যাট্রিক্সের কলাম সংখ্যা

• pq :=হিপ ব্যবহার করে একটি অগ্রাধিকার সারি তৈরি করুন এবং এতে [0, R-1, C-1, M[-1, -1]] ঢোকান

• dist :=একটি মানচিত্র

• dist[R-1, C-1, A[-1, -1]] :=0

• pq খালি না থাকার সময়, করুন

  • pq থেকে একটি উপাদান মুছে দিন এবং d, r, c, h

    এ সংরক্ষণ করুন

  • যদি dist[r, c, h]

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

  • যদি r এবং c উভয়ই 0 হয়, তাহলে

    • d

      ফেরত দিন

  • প্রতিটি জোড়ার জন্য (nr, nc) [[r+1, c], [r, c+1], [r-1, c], [r, c-1]], do

    • যদি 0 <=nr

      • যদি d2

        • dist[nr, nc, h2] :=d2

        • pq

          -এ [d2, nr, nc, h2] সন্নিবেশ করান

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

উদাহরণ

import collections
import heapq
class Solution:
   def solve(self, A):
      INF = float('inf')
      R, C = len(A), len(A[0])

      pq = [[0, R-1, C-1, A[-1][-1]]]
      dist = collections.defaultdict(lambda: INF)
      dist[R-1, C-1, A[-1][-1]] = 0
      while pq:
         d, r, c, h = heapq.heappop(pq)
         if dist[r, c, h] < d:
            continue
         if r == c == 0:
            return d
         for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
            if 0 <= nr < R and 0 <= nc < C:
               h2 = max(A[nr][nc], h)
               d2 = d + max(h2 - A[nr][nc], 0)
               if d2 < dist[nr, nc, h2]:
                  dist[nr, nc, h2] = d2
                  heapq.heappush(pq, [d2, nr, nc, h2])
ob = Solution()
matrix = [
[2, 4, 5],
[8, 6, 1]
]
print(ob.solve(matrix))

ইনপুট

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

আউটপুট

4