Tìm số bước nhảy tối thiểu để đến đích với 2 độ dài nhảy cho trước (Python)

Bài toán: Từ vị trí p, có thể nhảy trái/phải d1 hoặc d2 đơn vị. Tìm số bước tối thiểu đến q.

Thuật toán BFS

Trạng thái: (vị trí hiện tại, số bước). Dùng BFS để tìm đường đi ngắn nhất. Cần kiểm tra tính khả thi trước bằng GCD.

Triển khai Python

from math import gcd
from collections import deque

def solve(p, d1, d2, q):
    # Kiểm tra khả thi: (p-q) phải chia hết cho gcd(d1,d2)
    gcd_val = gcd(d1, d2)
    if (p - q) % gcd_val != 0:
        return -1
    
    que = deque()
    visited = set()
    que.appendleft([p, 0])
    visited.add(p)
    
    while que:
        pos, steps = que.pop()
        if pos == q:
            return steps
        
        for next_pos in (pos + d1, pos + d2, pos - d1, pos - d2):
            if next_pos not in visited:
                visited.add(next_pos)
                que.appendleft([next_pos, steps + 1])
    
    return -1  # Unreachable (shouldn't happen if gcd check passed)

# Test
print(solve(5, 4, 3, 10))  # 3: 5→9(+4)→13(+4)→10(-3)
print(solve(0, 2, 4, 7))   # -1: gcd(2,4)=2, 7%2=1 → impossible

Kết quả

True

Giải thích

• Kiểm tra GCD trước: gcd(d1,d2) phải chia hết |p-q| (điều kiện cần và đủ cho bài toán coin change / linear Diophantine).
• BFS từ p, 4 hướng nhảy: ±d1, ±d2.
• Dùng deque và set visited.
• Độ phức tạp: O(|p-q|/gcd) trạng thái, có thể lớn nếu khoảng cách xa.
• Có thể tối ưu bằng thuật toán Euclid mở rộng hoặc math formula cho 2 bước nhảy.