d094: Q-7-5. 闖關路線 (APCS201910)
Tags : BFS 圖論
Accepted rate : 54人/61人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-07-08 18:20

Content

某個闖關遊戲上有一隻神奇寶貝與兩個可控制左右移動的按鍵。神奇寶貝被安置在僅

可左右移動的滑軌上。滑軌分成 n 個位置,由左到右分別以 0 ~ n - 1 表示。當遊

戲開始時,神奇寶貝從位置 0 開始,遊戲的資訊包含 P、L 與 R 三個數字,其中 P 表

示所須移至的目標位置,L 與 R 則分別表示每按一次左鍵或右鍵後,會往左或往右移

動的格子數。此外,每一個位置 x 都對應一個瞬間移動位置 S(x);每一次按鍵後,

神奇寶貝會先依據按鍵往左或右移動到某個位置 x,接著瞬間移動至 S(x)。某些點

的瞬間移動位置等同原地點,也就是 S(x) = x,這些點稱為停留點。開始與目標位

置都一定是停留點;此外,每個點的瞬間移動位置都一定是停留點(除非超出界外),

也就是不會發生連續瞬間移動的情形。

遊戲的目標是以最少的按鍵數操作神奇寶貝由開始位置到達目標位置,此外,在移動

過程中不可以超過滑軌的範圍[0, n - 1],否則算闖關失敗;某些點的瞬間移動位

置也可能會超出滑軌的範圍,移動到這些點也會導致闖關失敗。

Input

輸入有兩行,第一行有 4 個數字,第 1 個為 n,第 2 個為目標位置 P,第

3 個為 L,第 4 個為 R,後三個數字皆為小於 n 之正整數,且 2 ≤ n ≤ 1e6。第二

行有 n 個整數,依序是各點的瞬間移動位置 S(0), S(1), …, S(n - 1),這些數

字是絕對值不超過 1e8 的整數。

Output

輸出到達目標位置所需的最少按鍵數,如果無法到達目標位置,則輸出 -1。

Sample Input
// 1
5 3 1 2
0 3 2 3 5
// 2
10 8 2 3
0 5 2 3 4 5 6 6 8 9
Sample Output
// 1
2
// 2
3
測資資訊:
記憶體限制: 160 MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <10M
不公開 測資點#3 (20%): 1.0s , <10M
不公開 測資點#4 (20%): 1.0s , <10M
Hint :

 考量 Python 使用者,記憶體限制目前自 64MiB 放寬至 160MiB.

 

$nevikw39$

Tags:
BFS 圖論
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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