f166. 傳送點
Tags : BFS
Accepted rate : 37人/63人 ( 59% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-06 01:37

Content

有 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。

Input

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

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

Output

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

Sample Input #1
5 3 1 2
0 2 4 3 1
Sample Output #1
2
測資資訊:
記憶體限制: 64 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
Hint :
Tags:
BFS
出處:
2019年10月APCS [管理者: mushroom.cs9...(mushroom) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」