Python में न्यूनतम प्रयास वाला पथ खोजने का प्रोग्राम

मान लीजिए हमारे पास height नामक एक m x n क्रम का 2D मैट्रिक्स है। heights[i][j] सेल (i, j) की ऊंचाई दर्शाता है। यदि हम (0, 0) सेल पर हैं तो हम नीचे-दाएं सेल (m-1, n-1) तक यात्रा करना चाहते हैं। हम ऊपर, नीचे, बाएं, या दाएं जा सकते हैं, और हम एक ऐसा रास्ता ढूंढना चाहते हैं जिसमें न्यूनतम प्रयास की आवश्यकता हो। इस समस्या में रूट का प्रयास रूट के दो लगातार सेल्स के बीच ऊंचाई में अधिकतम निरपेक्ष अंतर है। तो अंत में, हमें गंतव्य तक यात्रा करने के लिए आवश्यक न्यूनतम प्रयास ढूंढना है।

उदाहरण के लिए, यदि इनपुट है:

2	3	4
4	9	5
6	4	6

तो आउटपुट 1 होगा क्योंकि रास्ता [2,3,4,5,6] है जिसमें लगातार सेल्स में अधिकतम निरपेक्ष अंतर 1 है।

समाधान के चरण

r := len(heights), c := len(heights[0])
queue := [(0,0,0)] (प्रारंभ में एक टपल स्टोर करने वाली क्यू)
while queue:
- cur := heapq.heappop(queue)
- c_eff := cur[0]
- x := cur[1]
- y := cur[2]
- यदि x == r-1 and y == c-1:
  - c_eff वापस करें
- यदि heights[x][y] == "":
  - अगले इटरेशन पर जाएं
- [[1,0],[-1,0],[0,1],[0,-1]] में प्रत्येक dx,dy के लिए:
  - newx := x+dx
  - newy := y+dy
  - यदि 0 <= newx < r and 0 <= newy < c and heights[newx][newy] != "":
    - eff := max(c_eff, abs(heights[newx][newy] - heights[x][y]))
    - heapq.heappush(queue, (eff, newx, newy))
- heights[x][y] := ""

उदाहरण

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

import heapq

def solve(heights):
    r, c = len(heights), len(heights[0])
    queue = [(0, 0, 0)]
    while queue:
        cur = heapq.heappop(queue)
        c_eff = cur[0]
        x = cur[1]
        y = cur[2]
        if x == r-1 and y == c-1:
            return c_eff
        if heights[x][y] == "":
            continue
        for dx, dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            newx = x + dx
            newy = y + dy
            if 0 <= newx < r and 0 <= newy < c and heights[newx][newy] != "":
                eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
                heapq.heappush(queue, (eff, newx, newy))
        heights[x][y] = ""

matrix = [[2,3,4],[4,9,5],[6,4,6]]
print(solve(matrix))

इनपुट

[[2,3,4],[4,9,5],[6,4,6]]