【題解】TCIRC d094: Q-7-5. 闖關路線 (APCS201910)

【題目敘述】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;
}
分享本文 Share with friends