पायथन में अधिकतम न्यूनतम मूल्य वाला पथ

मान लीजिए कि हमारे पास आर पंक्तियों और सी कॉलम के साथ पूर्णांकों का एक मैट्रिक्स ए है, हमें [0,0] से शुरू होने वाले और [आर-1, सी-1] पर समाप्त होने वाले पथ का अधिकतम स्कोर खोजना होगा। यहां स्कोरिंग तकनीक उस पथ में न्यूनतम मान होगी। उदाहरण के लिए, पथ 8 → 4 → 5 → 9 का मान 4 है। एक पथ 4 कार्डिनल दिशाओं (उत्तर, पूर्व, पश्चिम, दक्षिण) में से किसी एक में एक विज़िट किए गए सेल से किसी भी पड़ोसी अनजान सेल में कई बार चलता है। ।

उदाहरण के लिए, यदि ग्रिड की तरह है -

नारंगी कोशिकाएं पथ होंगी। आउटपुट 4

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

• r :=पंक्तियों की संख्या और c :=स्तंभों की संख्या
• Ans :=न्यूनतम A[0, 0] और A[r-1, c-1]
• एक मैट्रिक्स बनाएं जिसे विज़िट किया गया ऑर्डर A के समान कहा जाता है, और इसे FALSE से भरें
• h :=एक सूची, जहां हम एक टपल स्टोर करते हैं (-A[0, 0], 0, 0)
• एच से ढेर बनाएं
• जबकि h खाली नहीं है
  • v, x, y :=h को हीप से डिलीट करें, और तीन मानों को स्टोर करें
  • यदि x =r – 1 और y :=c – 1, तो लूप से बाहर आएं
  • उत्तर :=न्यूनतम उत्तर, A[x, y]
  • विज़िट किया[x, y] :=true
  • डाई के लिए, सूची में डीएक्स [(-1, 0), (1, 0), (0, 1), (0, -1)], करो
    • a :=x + dx और b :=y + dy
    • यदि a 0 से r – 1 की श्रेणी में और b श्रेणी 0 से c – 1 में है और विज़िट किया गया है[a, b] गलत है,
      • एच के साथ ढेर में (-ए [ए, बी], ए, बी) डालें
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

import heapq
class Solution(object):
   def maximumMinimumPath(self, A):
      """
      :type A: List[List[int]]
      :rtype: int
      """
      r,c = len(A),len(A[0])
      ans = min(A[0][0],A[-1][-1])
      visited = [[False for i in range(c)] for j in range(r)]
      h = [(-A[0][0],0,0)]
      heapq.heapify(h)
      while h:
         # print(h)
         v,x,y = heapq.heappop(h)
         if x== r-1 and y == c-1:
            break
         ans = min(ans,A[x][y])
         visited[x][y]= True
         for dx,dy in {(-1,0),(1,0),(0,1),(0,-1)}:
            a,b = x+dx,y+dy
            if a>=0 and a<r and b>=0 and b<c and not visited[a][b]:
               heapq.heappush(h,(-A[a][b],a,b))
      return ans

इनपुट

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

आउटपुट

4