เริ่มที่ p กระโดดซ้าย/ขวา d1, d2 หา Min Steps ไป q
เช่น Input p = 5, q = 10, d1 = 4, d2 = 3 Output 3 (Right 4, Right 4 -> 13, Left 3 -> 10)
ขั้นตอนแก้ (BFS):
- GCD(d1,d2) ต้องหาร (p-q) ลงตัว มิฉะนั้น -1
- BFS จาก p ด้วย Queue เก็บ (position, steps)
- Visited Set ป้องกันซ้ำ
- Expand: pos ± d1, pos ± d2
ตัวอย่างโค้ด
from math import gcd
from collections import deque
def solve(p, d1, d2, q):
gcd_res = gcd(d1, d2)
if (p - q) % gcd_res != 0:
return -1
que = deque()
visited = set()
que.appendleft([p, 0])
visited.add(p)
while len(que) > 0:
pair = que.pop()
point, step = pair[0], pair[1]
if point == q:
return step
if point + d1 not in visited:
que.appendleft([(point + d1), step + 1])
visited.add(point + d1)
if point + d2 not in visited:
que.appendleft([(point + d2), step + 1])
visited.add(point + d2)
if point - d1 not in visited:
que.appendleft([(point - d1), step + 1])
visited.add(point - d1)
if point - d2 not in visited:
que.appendleft([(point - d2), step + 1])
visited.add(point - d2)
p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))
Input
5, 4, 3, 10
Output
True
