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

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

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

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

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

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

उदाहरण

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

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