โปรแกรมหาการเคลื่อนไหวขั้นต่ำในเกมงูและบันไดใน Python

สมมติว่าเรากำลังเล่นเกมงูและบันได เรามีเงื่อนไขว่าเราจะทอยเลขอะไรก็ได้ที่เราชอบบนลูกเต๋า เราเริ่มจากตำแหน่ง 0 และปลายทางของเราคือตำแหน่ง 100 และเราทอยลูกเต๋าหลายครั้งเพื่อไปถึงจุดหมาย เราต้องค้นหาจำนวนการทอยลูกเต๋าให้น้อยที่สุดเพื่อไปให้ถึงปลายทางหากเราจัดให้มีตำแหน่งของงูและบันไดบนกระดาน งูและบันไดเรียงแถวเป็นตัวแทนของตำแหน่งของงูและบันไดในกระดานและแต่ละรายการใน อาร์เรย์ประกอบด้วยค่าเริ่มต้นและค่าสิ้นสุดของงูหรือบันไดบนกระดาน

ดังนั้น ถ้าอินพุตเป็นเหมือนบันได =[(11, 40), (37,67),(47, 73),(15, 72)], งู =[(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)] จากนั้นผลลัพธ์จะเป็น 8

จำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นคือ 8 เพื่อให้ถึงตำแหน่งที่ 100 บนกระดานตามตำแหน่งของงูและบันได

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ต่อท้ายอาร์เรย์งูเข้ากับบันไดอาร์เรย์
• ขอบ :=แผนที่ใหม่
• สำหรับแต่ละคู่ f,t ในบันได ทำ
  • ขอบ[f] :=t
• u :=ชุดใหม่
• v :=ชุดใหม่
• เพิ่ม(1) ไปยัง v
• ม :=0
• ในขณะที่ไม่มี 100 ใน v ให้ทำ
  • ม :=ม + 1
  • w :=ชุดใหม่
  • สำหรับแต่ละ f ใน v ทำ
    • สำหรับผมในช่วง 1 ถึง 6 ทำ
      • n :=f + i
      • ถ้ามี n อยู่ที่ขอบ แล้ว
        • n :=ขอบ[n]
      • ถ้า n มีอยู่ใน u แล้ว
        • ติดตามตอนต่อไป
      • เพิ่ม(n) ให้กับคุณ
      • เพิ่ม(n) ให้กับ w
  • v :=w
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

defแก้ปัญหา(บันได, งู):ladders.extend (งู) ขอบ ={} สำหรับ f,t ในบันได:ขอบ[f] =t u =set() v =set() v.add(1) m =0 ในขณะที่ 100 ไม่อยู่ใน v:m +=1 w =set() สำหรับ f ใน v:สำหรับฉัน อยู่ในช่วง (1,7):n =f + i ถ้า n ในขอบ:n =ขอบ[n] ถ้า n ใน u:ทำต่อ u.add(n) w.add(n) v =w return mprint(solve([(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

อินพุต

ผลลัพธ์

8