f166. 傳送點
標籤 : BFS
通過比率 : 318人/401人 ( 79% ) [非即時]
評分方式:
Tolerant

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

內容

有 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 ≤ 106
0 ≤ P ≤ n-1
1 ≤ L,R ≤ n/2

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

輸出說明

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

範例輸入 #1
5 3 1 2
0 2 4 3 1
範例輸出 #1
2
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
BFS
出處:
2019年10月APCS [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

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