पायथन में सांप-सीढ़ी खेल में न्यूनतम चालें ज्ञात करने का प्रोग्राम

मान लीजिए हम सांप-सीढ़ी का खेल खेल रहे हैं। हमारे पास एक शर्त है कि हम पासे पर कोई भी संख्या प्राप्त कर सकते हैं। हम स्थिति 0 से शुरू करते हैं और हमारा गंतव्य स्थिति 100 है, और हम गंतव्य तक पहुंचने के लिए कई बार पासा फेंकते हैं। यदि हमें बोर्ड पर सांपों और सीढ़ियों की स्थिति दी गई है, तो हमें गंतव्य तक पहुंचने के लिए आवश्यक पासा फेंकने की न्यूनतम संख्या ज्ञात करनी होगी। सरणियाँ snakes और ladders बोर्ड पर सांपों और सीढ़ियों की स्थितियों को दर्शाती हैं और सरणियों में प्रत्येक प्रविष्टि में बोर्ड पर एक सांप या सीढ़ी का प्रारंभ मान और अंत मान होता है।

इसलिए, यदि इनपुट है ladders = [(11, 40), (37,67),(47, 73),(15, 72)], snakes = [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)], तो आउटपुट 8 होगा।

दिए गए सांपों और सीढ़ियों की स्थितियों के साथ बोर्ड पर 100वीं स्थिति तक पहुंचने के लिए आवश्यक न्यूनतम चालों की संख्या 8 है।

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

• सरणी snakes को सरणी ladders में जोड़ें
• edges := एक नया मैप
• ladders में प्रत्येक जोड़ी f,t के लिए, करें
  • edges[f] := t
• u := एक नया सेट
• v := एक नया सेट
• v में 1 जोड़ें
• m := 0
• जब तक 100 v में मौजूद नहीं है, करें
  • m := m + 1
  • w := एक नया सेट
  • v में प्रत्येक f के लिए, करें
    • i को 1 से 6 तक के लिए, करें
      • n := f + i
      • यदि n edges में मौजूद है, तो
        • n := edges[n]
      • यदि n u में मौजूद है, तो
        • अगली पुनरावृत्ति के लिए जाएं
      • n को u में जोड़ें
      • n को w में जोड़ें
  • v := w
• m वापस करें

उदाहरण

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

def solve(ladders, snakes):
    ladders.extend(snakes)
    edges = {}
    for f, t in ladders:
        edges[f] = t
    u = set()
    v = set()
    v.add(1)
    m = 0
    while 100 not in v:
        m += 1
        w = set()
        for f in v:
            for i in range(1, 7):
                n = f + i
                if n in edges:
                    n = edges[n]
                if n in u:
                    continue
                u.add(n)
                w.add(n)
        v = w
    return m

print(solve([(11, 40), (37, 67), (47, 73), (15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

इनपुट

[(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

आउटपुट

8