【題目敘述】https://judge.tcirc.tw/ShowProblem?problemid=d094
【解題想法】BFS 求最短路徑
- 跳躍的方式只有從位置 x 跳躍到位置 x+R，或是從位置 x 跳躍到位置 x-L。
- 每次神奇寶貝跳躍到某位置 x 的「瞬間」就會自動被移動到位置S(x)。
- 如果神奇寶貝「跳躍到的停留點」不在合法的滑軌位置上，「或是」「跳躍後被移動去的停留點」不在合法的滑軌位置上，他就不能進行這樣的跳躍。
- 資料預處理，只能在位置 0 ～ (n-1) 跳躍或瞬移，先把不合法的資料全都存成 n，後續的判斷比較方便。
- d[i]：抵達位置 i 的最短路徑。初始值設為 -1，表示還沒走過。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1000005;
int n, p, l, r, a[maxn], d[maxn], now, nxt;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> n >> p >> l >> r) {
for (int i = 0; i < n; i++){
cin >> a[i];
if (a[i] >= n || a[i] < 0) a[i] = n;
}
memset(d, -1, sizeof(d));
d[0] = 0;
queue <int> q;
q.push(0);
while (!q.empty() && d[p] == -1){
now = q.front();
q.pop();
nxt = now - l;
if (nxt >= 0 && a[nxt] != n && d[a[nxt]] == -1){
d[a[nxt]] = d[now] + 1;
q.push(a[nxt]);
}
nxt = now + r;
if (nxt < n && a[nxt] != n && d[a[nxt]] == -1){
d[a[nxt]] = d[now] + 1;
q.push(a[nxt]);
}
}
cout << d[p] << "\n";
}
return 0;
}