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

Python में अंतिम लक्ष्य तक पहुंचने के लिए आवश्यक न्यूनतम बसों की संख्या खोजने का प्रोग्राम


मान लीजिए हमारे पास एक n x 3 मैट्रिक्स है जहां प्रत्येक पंक्ति में तीन फ़ील्ड [src, dest, id] होते हैं इसका मतलब है कि बस का रूट src से dest तक है। एक नई बस में चढ़ने के लिए एक यूनिट पैसे लगते हैं, लेकिन अगर हम उसी बस पर रहते हैं तो हमें केवल एक यूनिट देना पड़ता है। हमें स्थान 0 से अंतिम स्टॉप (सबसे बड़ा स्थान) तक बस लेने के लिए आवश्यक न्यूनतम लागत ढूंढनी है। यदि कोई समाधान नहीं है तो -1 लौटाएं।

इसलिए, यदि इनपुट इस तरह है

010
120
230
351
502

तो आउटपुट 2 होगा, क्योंकि हम स्थान 0 पर बस 0 ले सकते हैं और स्थान 3 पर उतर सकते हैं। फिर हम बस 1 लेकर स्थान 5 तक पहुंच सकते हैं।

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

  • start := 0
  • target := दिए गए मैट्रिक्स का अधिकतम स्थान
  • adj := एक खाली मैप
  • प्रत्येक src, dest, id के लिए connections में, करें
    • (dest, id) को adj[src] के अंत में डालें
  • hp := आइटम (0, start, -1) के साथ एक हीप
  • seen := एक खाली मैप
  • जब तक hp खाली नहीं है, करें
    • (cost, cur_pos, cur_bus) := हीप hp का शीर्ष तत्व और hp से शीर्ष हटाएं
    • यदि cur_pos, target के समान है, तो
      • cost लौटाएं
    • यदि cur_bus, seen[cur_pos] में है, तो
      • अगले इटरेशन के लिए जाएं
    • cur_bus को seen[cur_pos] में डालें
    • cur_pos में प्रत्येक (nex_pos, nex_bus) के लिए adj में, करें
      • next_cost := cost
      • यदि nex_bus, cur_bus के समान नहीं है, तो
        • next_cost := next_cost + 1
      • (next_cost, nex_pos, nex_bus) को हीप hp में डालें
  • -1 लौटाएं

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

उदाहरण

from collections import defaultdict
from heapq import heapify, heappop, heappush
class Solution:
    def solve(self, connections):
        start = 0
        target = max(max(y, x) for y, x, _ in connections)
        adj = defaultdict(list)
        for f, t, id in connections:
            adj[f].append((t, id))
        hp = [(0, start, -1)]
        seen = defaultdict(set)
        while hp:
            cost, cur_pos, cur_bus = heappop(hp)
            if cur_pos == target:
                return cost
            if cur_bus in seen[cur_pos]:
                continue
            seen[cur_pos].add(cur_bus)
            for nex_pos, nex_bus in adj[cur_pos]:
                next_cost = cost
                if nex_bus != cur_bus:
                    next_cost += 1
                heappush(hp, (next_cost, nex_pos, nex_bus))
        return -1
ob = Solution()
matrix = [
    [0, 1, 0],
    [1, 2, 0],
    [2, 3, 0],
    [3, 5, 1],
    [5, 0, 2]
]
print(ob.solve(matrix))

इनपुट

matrix = [[0, 1, 0], [1, 2, 0], [2, 3, 0], [3, 5, 1], [5, 0, 2]]

आउटपुट

2
  1. - Python में घर पहुंचने के लिए न्यूनतम जंप खोजने का प्रोग्राम

    मान लीजिए एक ऐरे forbidden है, जहां forbidden[i] दर्शाता है कि बग forbidden[i] पोजीशन पर जंप नहीं कर सकता, और हमारे पास तीन मान a, b, और x भी हैं। एक बग का घर संख्या रेखा पर पोजीशन x पर है। यह शुरू में पोजीशन 0 पर है। यह निम्नलिखित नियमों से जंप कर सकता है: बग ठीक a पोजीशन दाएं जंप कर सकता है। बग

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

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

  1. पायथन में शतरंज के नाइट द्वारा टार्गेट पोजीशन तक पहुंचने के लिए न्यूनतम चालें खोजने का प्रोग्राम पायथन में शतरंज के नाइट द्वारा टार्गेट पोजीशन तक पहुंचने के लिए न्यूनतम चालें खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो मान r और c हैं। यदि एक शतरंज नाइट अनंत बड़े शतरंज बोर्ड पर निर्देशांक (0,0) पर रखा गया है, तो हमें (r,c) स्थान तक पहुंचने के लिए न्यूनतम चालों की संख्या ढूंढनी है। नाइट शतरंज की तरह चलता है: दो वर्ग क्षैतिज और एक लंबवत, या दो लंबवत और एक क्षैतिज।उदाहरण के लिए, यदि इनपुट r=6, c