मान लीजिए हमारे पास एक मैट्रिक्स M है जहां M[r][c] उस सेल की ऊंचाई दर्शाता है। यदि हम वर्तमान में ऊपरी बाएं कोने पर हैं और निचले दाएं कोने पर जाना चाहते हैं। हम आसन्न सेल (ऊपर, नीचे, बाएं, दाएं) पर तभी जा सकते हैं जब उस आसन्न सेल की ऊंचाई वर्तमान सेल की ऊंचाई से कम या बराबर हो। हम चलने से पहले किसी भी संख्या में सेल्स की ऊंचाई बढ़ा सकते हैं, इसलिए हमें न्यूनतम कुल ऊंचाई वृद्धि ढूंढनी है ताकि हम निचले दाएं सेल तक पहुंच सकें।
उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:
| 2 | 4 | 5 |
| 8 | 6 | 1 |
तो आउटपुट 4 होगा, क्योंकि हम निम्न पथ [2, 4, 5, 1] ले सकते हैं और ऊंचाइयों को इस विन्यास में बदल सकते हैं:
| 5 | 5 | 5 |
| 8 | 6 | 1 |
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (डिज्क्स्ट्रा जैसा दृष्टिकोण):
INF := infinity।R, C := मैट्रिक्स की पंक्तियाँ, स्तंभ।pq := प्रायोरिटी क्यू (हीप)जिसमें[0, R-1, C-1, M[-1][-1]]डालें।dist := डिफॉल्टडिक्ट(lambda: INF)।dist[R-1, C-1, M[-1][-1]] = 0।जब तक
pqखाली नहीं है:d, r, c, h = heapq.heappop(pq)।यदि
dist[r, c, h] < d, तो जारी रखें।यदि
r == 0 and c == 0, तोdलौटाएं।प्रत्येक पड़ोसी
(nr, nc)के लिए[[r+1,c], [r,c+1], [r-1,c], [r,c-1]]में:यदि
0 <= nr < R and 0 <= nc < C:h2 = max(M[nr][nc], h)।d2 = d + max(h2 - M[nr][nc], 0)।यदि
d2 < dist[nr, nc, h2], तो अपडेट करें औरpqमें डालें।
उदाहरण
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