Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

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


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

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

245
861

तो आउटपुट 4 होगा, क्योंकि हम निम्न पथ [2, 4, 5, 1] ले सकते हैं और ऊंचाइयों को इस विन्यास में बदल सकते हैं:

555
861

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (डिज्क्स्ट्रा जैसा दृष्टिकोण):

  • 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

  1. Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें? Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें?

    डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं। एल्गोरिदम सभी नोड्स का सेट बनाएं (0 से n-1)। सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं। सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)। यही मिनिमम वर्टेक्स सेट है। उद

  1. पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास रंगों (R, G, B) की एक लिस्ट है। अब यदि दो अलग-अलग रंग अगल-बगल हैं तो वे तीसरे रंग के एकल रंग आइटम में बदल सकते हैं। हमें किसी भी संभावित परिवर्तन अनुक्रम के बाद शेष सबसे छोटी संख्या ढूंढनी है।उदाहरण के लिए, यदि इनपुट colors = [G, R, G, B, R] है, तो आउटपुट 1 होगा क्योंकि यह नीचे द

  1. पायथन प्रोग्राम: संख्या के फैक्टर्स का न्यूनतम योग ढूंढें पायथन प्रोग्राम: संख्या के फैक्टर्स का न्यूनतम योग ढूंढें

    इस लेख में, हम नीचे दिए गए प्रॉब्लम स्टेटमेंट के समाधान के बारे में सीखेंगे: प्रॉब्लम स्टेटमेंट एक नंबर इनपुट दिए जाने पर, दी गई संख्या के फैक्टर्स का न्यूनतम योग ढूंढें। यहां हम सभी फैक्टर्स और उनके संबंधित योग की गणना करेंगे और फिर उनमें से न्यूनतम ढूंढेंगे। तो संख्या के गुणनफल का न्यूनतम योग ढू