题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki(K1=3,K2=3,……),从一楼开始。在一楼,按“上”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮呢?
输入输出格式
输入格式:输入文件共有二行,第一行为三个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N),第二行为N个用空格隔开的非负整数,表示Ki。
输出格式:输出文件仅一行,即最少按键次数,若无法到达,则输出-1。
输入输出样例
输入样例#1:5 1 5 3 3 1 2 5输出样例#1:
3
Solution:
本题,入眼搜索。直接dfs就ok了。这里我选择的是spfs跑最短路求解,首先将某一层连有向边到它能到达的层数并将边权设置为1,然后从s到t跑一遍最短路就ok了。
代码:
#include<bits/stdc++.h> #define il inline using namespace std; const int N=100005,inf=233333333; il int gi() { int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=a*10+x-48,x=getchar(); return f?-a:a; } int n,a,b,k,dis[500],h[N],cnt; struct edge{ int to,net,w; }e[N]; bool vis[N]; il void add(int u,int v,int w) { e[++cnt].to=v,e[cnt].net=h[u],e[cnt].w=w,h[u]=cnt; } il int spfa(int s,int t) { queue<int>q; for(int i=0;i<=200;i++)dis[i]=inf; q.push(s);dis[s]=0;vis[s]=1; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=h[u];i;i=e[i].net) { int v=e[i].to; if(dis[v]>dis[u]+1){ dis[v]=dis[u]+1; if(!vis[v])q.push(v),vis[v]=1; } } } return dis[t]; } int main() { n=gi(),a=gi(),b=gi(); for(int i=1;i<=n;i++){ k=gi(); if(k+i<=n)add(i,k+i,1); if(i-k>0)add(i,i-k,1); } int ans=spfa(a,b); printf("%d",ans==inf?-1:ans); return 0; }