สมมติว่ามีอาร์เรย์ที่เรียกว่าต้องห้าม โดยที่ต้องห้าม[i] ระบุว่าจุดบกพร่องไม่สามารถข้ามไปยังตำแหน่งที่ต้องห้าม[i] และเรายังมีค่าสามค่า a, b และ x บ้านของแมลงอยู่ที่ตำแหน่ง x บนเส้นจำนวน อยู่ที่ตำแหน่ง 0 ในตอนแรก มันสามารถกระโดดได้ตามกฎ -
-
แมลงกระโดดข้ามตำแหน่งไปทางขวาได้พอดี
-
แมลงสามารถข้ามตำแหน่ง b ไปทางซ้ายได้พอดี
-
บักไม่สามารถกระโดดถอยหลัง 2 ครั้งติดต่อกันได้
-
ข้อผิดพลาดไม่สามารถข้ามไปยังตำแหน่งที่ต้องห้ามในอาร์เรย์ได้
-
แมลงสามารถกระโดดไปข้างหน้าได้ แต่ไม่สามารถข้ามไปยังตำแหน่งที่มีค่าลบได้
เราต้องหาจำนวนการกระโดดขั้นต่ำที่จำเป็นสำหรับจุดบกพร่องเพื่อไปถึงปลายทาง หากไม่มีลำดับที่เป็นไปได้ดังกล่าว ให้คืนค่า -1
ดังนั้น ถ้าอินพุตเหมือนถูกห้าม =[2,3,7,9, 12], a =4, b =2, x =16 แล้วเอาท์พุตจะเป็น 7 เพราะเริ่มจาก 0 ให้กระโดด a =4 ไปข้างหน้า สองครั้งเพื่อไปถึง 4 และ 8 แต่ไม่สามารถข้ามไปที่ 12 ได้เนื่องจากถูกห้ามจากนั้นให้ถอยกลับ b =2 ที่ 6 จากนั้นข้ามไปที่ 10, 14, 18 และสองกลับไปถึง 16 จึงมี 7 ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
คิว :=คิวที่มีทูเพิล (x,0,True) ต้องห้าม :=ชุดใหม่และแทรกองค์ประกอบจากรายการต้องห้าม
-
lim :=a + b + (สูงสุด x และค่าสูงสุดของชุดต้องห้าม)
-
ขณะที่คิวไม่ว่างให้ทำ
-
(curr,jumps,is_b) :=องค์ประกอบแรกจากคิวและลบออกจากคิว
-
ถ้า curr อยู่ในสิ่งต้องห้ามหรือ (0 <=curr <=lim) เป็นเท็จ แล้ว
-
ไปทำซ้ำต่อไป
-
-
ใส่ลูกเกดเข้าที่ต้องห้าม
-
ถ้าค่าเงินเท่ากับ 0 แล้ว
-
กระโดดกลับ
-
-
ถ้า is_b เป็นจริง
-
แทรก (curr+b,jumps+1,False) ลงในคิว
-
-
แทรก (curr-a,jumps+1,True) ลงในคิว
-
-
กลับ -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
