/**
* BFS
*还可以使用DP来解决,不过DP学的不好。没有尝试
*/
#include<stdio.h> #include<queue> using namespace std; int flag[210],data[210]; //flag用来标记当前楼梯所在层数是否已经搜索过。如果已经搜索过就不再加入队列中。 //避免重复的搜索 int N,A,B; struct Node{ int cur;//当前所在的楼梯层 int num;//次数 }; //BFS int search(){ Node t,temp; t.cur=A; t.num=0; queue<Node> Q; Q.push(t); flag[A]=1; int up,down; while(!Q.empty()){ temp = Q.front(); Q.pop(); if(temp.cur==B)return temp.num;//到达目的,返回次数 up=temp.cur+data[temp.cur];//向上 if(flag[up]==0 && up<=N){//是否可以向上走 flag[up]=1; t.cur=up; t.num=temp.num+1; Q.push(t); } down=temp.cur-data[temp.cur];//向下 if(flag[down]==0 && down>0){//是否可以向下走 flag[down]=1; t.cur=down; t.num=temp.num+1; Q.push(t); } } return -1;//无法达到 } int main(){ int i; while(scanf("%d",&N)&&N){ memset(flag,0,sizeof(flag)); scanf("%d%d",&A,&B); for(i=1;i<=N;i++){ scanf("%d",&data[i]); } printf("%d\n",search()); } return 0; }