สมมติว่าเราอยู่ที่ตำแหน่งเริ่มต้น p เราสามารถกระโดดไปในทิศทางใดก็ได้ (ซ้ายหรือขวา) d1 และ d2 หน่วย เราต้องหาจำนวนขั้นขั้นต่ำที่จำเป็นในการไปถึงตำแหน่ง q โดยกระโดดจาก p
ดังนั้น ถ้าอินพุตเท่ากับ p =5, q =10, d1 =4, d2 =3 แล้วเอาต์พุตจะเป็น 3 เนื่องจากเราสามารถกระโดดไปทางขวาได้โดยใช้ระยะทาง 4 สองครั้ง เราก็จะไปถึงตำแหน่ง 13 แล้วกระโดดไปทางซ้าย 3 หน่วยถึง 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- gcd_res :=gcd ของ d1 และ d2
- ถ้า (p - q) ไม่หารด้วย gcd_res แล้ว
- คืน -1
- que :=กำหนดหนึ่งคิวสิ้นสุดคู่
- เข้าชมแล้ว :=ชุดใหม่
- แทรกคู่ (p, 0) ลงในคิว
- ทำเครื่องหมาย p ว่าเข้าชมแล้ว
- ในขณะที่ขนาดของ que> 0 ไม่ใช่ศูนย์ ให้ทำ
- (ชี้, ขั้นตอน) :=องค์ประกอบด้านหน้าของคิวและลบออกจาก que
- ถ้าจุดเหมือนกับ q แล้ว
- ขั้นตอนการคืนสินค้า
- ถ้าไม่ได้ไปที่จุด + d1 แล้ว
- แทรกคู่ (จุด + d1, ขั้นตอน + 1) ลงใน que
- ทำเครื่องหมาย (จุด + d1) ว่าเข้าชมแล้ว
- ถ้าจุด + d2 ไม่อยู่ในการเยี่ยมชมนั้นไม่ใช่ศูนย์ ดังนั้น
- แทรกคู่ (จุด + d2, ขั้นตอน + 1) ลงใน que
- ทำเครื่องหมาย (จุด + d2) ว่าเข้าชมแล้ว
- ถ้าจุด - d1 ไม่ได้เข้าเยี่ยมชมนั้นไม่ใช่ศูนย์ ดังนั้น
- ใส่คู่ (จุด - d1, ขั้นตอน + 1) ลงใน que
- ทำเครื่องหมาย (จุด - d1) ว่าเข้าชมแล้ว
- ถ้าจุด - d2 ไม่ได้เยี่ยมชมนั้นไม่ใช่ศูนย์ ดังนั้น
- แทรกคู่ (จุด - d2, ขั้นตอน + 1) ลงใน que
- ทำเครื่องหมาย (จุด - 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))
อินพุต
5, 4, 3, 10
ผลลัพธ์
True
