Chương trình tìm số nhảy tối thiểu để về nhà trong Python

Con bọ ở vị trí 0, nhà ở x. Mảng forbidden các vị trí cấm. Quy tắc: nhảy phải đúng a (phải), nhảy trái đúng b; không nhảy trái 2 lần liên tiếp; không nhảy vào forbidden; không nhảy ra vị trí âm. Tìm số nhảy nhỏ nhất về x, -1 nếu không thể.

Ví dụ: forbidden=[2,3,7,9,12], a=4, b=2, x=16 → 7. Đường đi: 0→4→8→(12 cấm)→lùi 6→10→14→18→lùi 16 (7 bước).

Giải thuật (BFS ngược từ x về 0)

1. BFS từ x về 0 (ngược lại để dễ kiểm tra điều kiện không nhảy trái 2 lần).
2. Queue lưu (curr, jumps, is_back), is_back = True nếu bước trước nhảy trái.
3. Giới hạn lim = max(max(forbidden), x) + a + b.
4. Khi ra khỏi queue: bỏ qua nếu curr forbidden hoặc ngoài [0, lim]. Đánh dấu visited bằng cách thêm vào forbidden.
5. Nếu curr == 0: trả về jumps.
6. Mở rộng: nếu is_back có thể nhảy phải (curr+a); luôn có thể nhảy trái (curr-b) với is_back=True.

Ví dụ minh họa

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, b, x = 4, 2, 16
print(solve(forbidden, a, b, x))

Đầu vào

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

Đầu ra

7