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

ปัญหา

แมลงอยู่ที่ 0 บนเส้นจำนวน บ้านอยู่ที่ x มี forbidden ตำแหน่งห้ามกระโดด กฎ: กระโดดขวา a หน่วย, กระโดดซ้าย b หน่วย, ห้ามกระโดดซ้ายติดกัน 2 ครั้ง, ห้ามไปตำแหน่งติดลบ หาจำนวนกระโดดน้อยที่สุดถึง x มิฉะนั้น -1

ตัวอย่าง

forbidden=[2,3,7,9,12], a=4, b=2, x=16 → ผลลัพธ์ 7 (0→4→8→(ไม่ไป12)→6→10→14→18→16)

ขั้นตอนการแก้ปัญหา

1. BFS จาก x กลับไป 0: queue := [(x, 0, True)], forbidden := set(forbidden)
2. lim := max(max(forbidden), x) + a + b
3. بينما queue:
   • curr, jumps, is_b := queue.pop(0)
   • ถ้า curr in forbidden หรือไม่อยู่ใน [0, lim]: continue
   • เพิ่ม curr เข้า forbidden (ป้องกันซ้ำ)
   • ถ้า curr == 0: คืน jumps
   • ถ้า is_b: queue.append((curr+b, jumps+1, False))
   • queue.append((curr-a, jumps+1, True))
4. คืน -1

การนำไปใช้งาน (Python)

def solve(forbidden, a, b, x):
    queue, forbidden = [(x, 0, True)], set(forbidden)
    lim = max(max(forbidden), x) + a + b
    while queue:
        curr, jumps, is_b = queue.pop(0)
        if curr in forbidden or not 0 <= curr <= lim:
            continue
        forbidden.add(curr)
        if curr == 0:
            return jumps
        if is_b:
            queue.append((curr + b, jumps + 1, False))
        queue.append((curr - a, jumps + 1, True))
    return -1

forbidden = [2,3,7,9,12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))

อินพุต

[2,3,7,9,12], 4, 2, 16

เอาต์พุต

7