पायथन में गंतव्य तक पहुंचने के लिए न्यूनतम संख्या में ऊंचाई बढ़ाने का कार्यक्रम

मान लीजिए कि हमारे पास एक मैट्रिक्स एम है जहां एम [आर] [सी] उस सेल की ऊंचाई का प्रतिनिधित्व करता है। अगर हम वर्तमान में ऊपरी बाएँ कोने में हैं और नीचे दाएँ कोने में जाना चाहते हैं। हम आसन्न कोशिकाओं (ऊपर, नीचे, बाएँ, दाएँ) में तभी जा सकते हैं जब उस आसन्न कोशिका की ऊँचाई वर्तमान कोशिका की ऊँचाई से कम या उसके बराबर हो। आगे बढ़ने से पहले हम किसी भी संख्या में सेल की ऊंचाई बढ़ा सकते हैं, इसलिए हमें न्यूनतम कुल ऊंचाई ढूंढनी होगी जिसे बढ़ाने की जरूरत है ताकि हम नीचे दाएं सेल में जा सकें।

तो, अगर इनपुट पसंद है

तो आउटपुट 4 होगा, क्योंकि हम निम्नलिखित पथ [2, 4, 5, 1] ​​ले सकते हैं और ऊंचाई को इस कॉन्फ़िगरेशन में बदल सकते हैं -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

आईएनएफ:=अनंत

• आर, सी:=मैट्रिक्स की पंक्ति संख्या, मैट्रिक्स की कॉलम संख्या

• pq :=हीप का उपयोग करके एक प्राथमिकता कतार बनाएं, और उसमें [0, R-1, C-1, M[-1, -1]] डालें

• जिला:=एक नक्शा

• जिला[आर-1, सी-1, ए[-1, -1]] :=0

• जबकि pq खाली नहीं है, करें

  • pq से एक तत्व हटाएं और उन्हें d, r, c, h में संग्रहीत करें

  • अगर जिला [आर, सी, एच] <डी, फिर

    • अगले पुनरावृत्ति के लिए जाएं

  • अगर r और c दोनों 0 हैं, तो

    • वापसी d

  • [[r+1, c], [r, c+1], [r-1, c], [r, c-1]] में प्रत्येक जोड़ी (nr, nc) के लिए, do

    • अगर 0 <=एनआर <आर और 0 <=एनसी <सी, तो

      • अगर d2 <जिला[एनआर, एनसी, एच2], तो

        • जिला [एनआर, एनसी, एच 2]:=डी 2

        • 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