f166. 傳送點 - 高中生程式解題系統

內容

有 n 個格子由左至右編號為 0 到 n−1，
現在皮卡丘在起始位置編號 0 的位置，想要走到編號 P 的位置，
每次他都可以往左走 L 格或往右走 R 格。

對於每個格子，都有一個對應的傳送點 S。
在完成向左或向右的操作後，如果走到的格子為 i，皮卡丘將會瞬間被傳送到 S(i)，
S(i) 也有可能恰等於 i，即不傳送，此時 i 被稱為停留點。
其中起點和目標位置必為停留點，即 S(0) = 0、S(P) = P

當傳送發生後，不能發生連續傳送的情況，
也就是被傳送到 S(i) 後，不會再次被傳送到S(S(i))，
皮卡丘都必須在目前位置，再次選擇往左或往右走。

需要注意的是，當走出表格外時，會被認定為出界，
即不論是往左或往右或瞬間移動 S(i)，都不能夠走出表格外。

請問至少需要幾次操作，皮卡丘才能夠移動到 P；如果無解，則輸出 -1。

輸入說明

第一行包含四個整數 n, P, L, R
代表格子有 n 格，目標位置 P 和每次可以往左走 L 格或往右走 R 格
2 ≤ n ≤ 10⁶0 ≤ P ≤ n-1
1 ≤ L,R ≤ n/2

第二行有 n 個數字，由左至右，表示每個格子的傳送點 S(i)
S(0)、S(1)、……、S(n−1)
|S(i)| ≤ 10⁸

輸出說明

輸出跳躍到格子 P 所需的最少操作數，
若無法達成則輸出 -1

範例輸入 #1

5 3 1 2
0 2 4 3 1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (2%): 1.0s , <1K
公開測資點#1 (2%): 1.0s , <1K
公開測資點#2 (2%): 1.0s , <1K
公開測資點#3 (2%): 1.0s , <1K
公開測資點#4 (2%): 1.0s , <1K
公開測資點#5 (2%): 1.0s , <1K
公開測資點#6 (2%): 1.0s , <1K
公開測資點#7 (2%): 1.0s , <1K
公開測資點#8 (2%): 1.0s , <1K
公開測資點#9 (2%): 1.0s , <1K
公開測資點#10 (2%): 1.0s , <1K
公開測資點#11 (2%): 1.0s , <1K
公開測資點#12 (2%): 1.0s , <1K
公開測資點#13 (2%): 1.0s , <1K
公開測資點#14 (2%): 1.0s , <1K
公開測資點#15 (2%): 1.0s , <1K
公開測資點#16 (2%): 1.0s , <1K
公開測資點#17 (2%): 1.0s , <1K
公開測資點#18 (2%): 1.0s , <1K
公開測資點#19 (2%): 1.0s , <1K
公開測資點#20 (2%): 1.0s , <1K
公開測資點#21 (2%): 1.0s , <1K
公開測資點#22 (2%): 1.0s , <1K
公開測資點#23 (2%): 1.0s , <1K
公開測資點#24 (2%): 1.0s , <1K
公開測資點#25 (2%): 1.0s , <1K
公開測資點#26 (2%): 1.0s , <1K
公開測資點#27 (2%): 1.0s , <1K
公開測資點#28 (2%): 1.0s , <1K
公開測資點#29 (2%): 1.0s , <1K
公開測資點#30 (2%): 1.0s , <10M
公開測資點#31 (2%): 1.0s , <1M
公開測資點#32 (2%): 1.0s , <10M
公開測資點#33 (2%): 1.0s , <1M
公開測資點#34 (2%): 1.0s , <10M
公開測資點#35 (2%): 1.0s , <10M
公開測資點#36 (2%): 1.0s , <1M
公開測資點#37 (2%): 1.0s , <10M
公開測資點#38 (2%): 1.0s , <1M
公開測資點#39 (2%): 1.0s , <10M
公開測資點#40 (2%): 1.0s , <10M
公開測資點#41 (2%): 1.0s , <10M
公開測資點#42 (2%): 1.0s , <1M
公開測資點#43 (2%): 1.0s , <10M
公開測資點#44 (2%): 1.0s , <10M
公開測資點#45 (2%): 1.0s , <1M
公開測資點#46 (2%): 1.0s , <10M
公開測資點#47 (2%): 1.0s , <10M
公開測資點#48 (2%): 1.0s , <10M
公開測資點#49 (2%): 1.0s , <1M

提示：

標籤:

BFS

出處:

2019年 10月 APCS [管理者： mushroom.cs9 ... (mushroom) ]

編號	身分	題目	主題	人氣	發表日期
36876	hung100 (P.H.)	f166	⚠️注意⚠️	745	2023-08-14 12:14
41706	lbm00138 (bits/stdc++.h)	f166		106	2024-08-18 22:52