f166. 傳送點

解題

題目提到可以向左移動$L$格，跟向右移動$R$格，並且踩到的位置會進行傳送到對應的索引值$S_i$，並且不會二次傳送

我們可以用bfs為基底去做跳動的運算，這樣可以擴散我們走過的路徑，並且在走過的索引值上打上標記(走過的不走)避免無限迴圈，如果現在讀到的點是目標點，則跳出迴圈，並且輸出走過的路，如果執行到最後依然沒找到就回傳$-1$

如何做到計算層數的?
利用for迴圈，每次執行當前剛從while迴圈下來的長度次數，這就代表著這層的所有結點，只要把這層的節點全部走完就是距離+1

AC Code

python

from sys import stdin
from collections import deque
n,p,l,r=map(int,stdin.readline().strip().split())
row=list(map(int,stdin.readline().strip().split()))
def bfs():
    walk=[False]*n
    walk[0]=True
    q=deque([0])
    walks=0
    while q:
        temp=deque([])
        for _ in range(len(q)):
            idx=q.popleft()
            if idx==p: return walks
            if 0<=idx-l<n and 0<=row[idx-l]<n and not(walk[idx-l]):
                temp.append(row[idx-l])
                walk[idx-l]=True
            if 0<=idx+r<n and 0<=row[idx+r]<n and not(walk[idx+r]):
                temp.append(row[idx+r])
                walk[idx+r]=True
        q=temp
        walks+=1
    return -1
if p==0:
    print(p)
else:
    print(bfs())

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p,l,r;
ll bfs(const vector<ll>& rows){
    vector<bool> walk(n);
    for(ll i=0;i<n;i++) walk[i]=false;
    walk[0]=true;
    ll walks=0;
    queue<ll> q;
    q.push(0);
    while(!q.empty()){
        queue<ll> temp;
        ll sz=q.size();
        for(ll i=0;i<sz;i++){
            ll idx=q.front();
            q.pop();
            if(idx==p) return walks;
            if(0<=idx-l && 0<=rows[idx-l] && rows[idx-l]<n && !walk[idx-l]){
                temp.push(rows[idx-l]);
                walk[idx-l]=true;
            }
            if(idx+r<n && 0<=rows[idx+r] && rows[idx+r]<n && !walk[idx+r]){
                temp.push(rows[idx+r]);
                walk[idx+r]=true;
            }
        }
        walks++;
        q=temp;
    }
    return -1;
}
int main(){
    cin>>n>>p>>l>>r;
    vector<ll> row(n);
    for(ll i=0;i<n;i++){
        cin>>row[i];
    }
    if(p==0) cout<<p<<endl;
    else cout<<bfs(row)<<endl;
}