โปรแกรมหาจำนวนการทอยลูกเต๋าน้อยที่สุดในเกมงูและบันไดด้วย Python

สมมติว่าเรากำลังเล่นเกมงูและบันได เรามีเงื่อนไขว่าสามารถทอยลูกเต๋าได้ตัวเลขใดก็ตามที่ต้องการ เริ่มจากตำแหน่ง 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 จำนวนการเคลื่อนที่ขั้นต่ำคือ 8 เพื่อไปถึงตำแหน่งที่ 100 บนกระดานโดยคำนึงถึงตำแหน่งของงูและบันได

วิธีแก้ปัญหา

• ต่ออาร์เรย์ snakes เข้ากับ ladders
• edges := แมปใหม่
• สำหรับแต่ละคู่ f,t ใน ladders: edges[f] := t
• u := เซตใหม่, v := เซตใหม่
• เพิ่ม 1 ลง v
• m := 0
• while 100 ไม่อยู่ใน v:
  • m := m + 1
  • w := เซตใหม่
  • สำหรับแต่ละ f ใน v:
    • สำหรับ i ในช่วง 1 ถึง 6:
      • n := f + i
      • ถ้า n อยู่ใน edges: n := edges[n]
      • ถ้า n อยู่ใน u: ข้ามรอบถัดไป
      • เพิ่ม n ลง u และ w
  • v := w
• return 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