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

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

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

5	4	5
1	2	6
7	4	6

नारंगी सेल पथ होंगे। आउटपुट 4 है।

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

r := पंक्तियों की संख्या और c := कॉलम की संख्या
ans := A[0, 0] और A[r - 1, c - 1] का न्यूनतम
A के समान ऑर्डर का एक मैट्रिक्स visited बनाएं, और इसे FALSE से भरें
h := एक लिस्ट, जहां हम टपल (-A[0, 0], 0, 0) स्टोर करते हैं
h से हीप बनाएं
जब तक h खाली नहीं है
- v, x, y := हीप से h डिलीट करें, और तीन मान स्टोर करें
- यदि x = r - 1 और y := c - 1, तो लूप से बाहर आएं
- ans := ans, A[x, y] का न्यूनतम
- visited[x, y] := true
- लिस्ट [(-1, 0), (1, 0), (0, 1), (0, -1)] में प्रत्येक dy, dx के लिए, करें
  - a := x + dx और b := y + dy
  - यदि a रेंज 0 से r - 1 में है और b रेंज 0 से c - 1 में है और visited[a, b] false है,
    - (-A[a, b], a, b) को हीप h के साथ इन्सर्ट करें
ans लौटाएं

उदाहरण

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=0 and bइनपुट
[[5,4,5],[1,2,6],[7,4,6]]
आउटपुट
4