记录一个菜逼的成长。。
题目链接
题目大意： 给你n个数， a1,a2,...,an 表示在第i个点可以跳向 i+ai 点或 i−ai 点， 输出从每个点开始，跳向最后一个点步数。
我们可以反着做，从最后一个点开始bfs，搜能跳向当前点的点。
#include <bits/stdc++.h> using namespace std; #define ALL(v) (v).begin(),(v).end() #define cl(a,b) memset(a,b,sizeof(a)) #define clr clear() #define pb push_back typedef long long LL; template <typename T> inline void read(T &x){ T ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; x = ans; } /******************head***********************/ const int maxn = 100000 + 10; int vis[maxn],a[maxn],step[maxn],n; vector<int>ve[maxn]; void bfs(int x) { queue<int>q; q.push(x); cl(vis,0);cl(step,-1); vis[x] = 1;step[x] = 0; int s = 1,cnt = 1,tmp = 0; while(!q.empty()){ int f = q.front();q.pop(); if(cnt)cnt--; for( int i = 0; i < ve[f].size(); i++ ){ int v = ve[f][i]; if(!vis[v] && (v+a[v] == f || v-a[v] == f)){ vis[v] = 1; step[v] = s; q.push(v); tmp++; } } if(!cnt){cnt = tmp,tmp = 0,s++;} } } int main() { freopen("jumping.in","r",stdin); int T;scanf("%d",&T); while(T--){ scanf("%d",&n); for( int i = 1; i <= n; i++ )ve[i].clr; for( int i = 1; i <= n; i++ ){ read(a[i]); ve[min(i+a[i],n)].pb(i); ve[max(0,i-a[i])].pb(i); } bfs(n); for( int i = 1; i <= n; i++ ){ printf("%d\n",step[i]); } } return 0; }