Description

There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can't go up high than N,and can't go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can't do it, because it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist. 
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button "UP" or "DOWN"? 

**
Input**

The input consists of several test cases.,Each test case contains two lines. 
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,….kn. 
A single 0 indicate the end of the input.

Output

For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can't reach floor B,printf "-1".Sample Input

5 1 5
3 3 1 2 5
0

Sample Output

3

第一种解法：使用BFS，这里需要考虑到队列中楼层重复的问题，所有设置了一个vis来避免相同数据加入。

#include
#include
#include
#include
using namespace std;
bool vis[210];
struct node{
int num;
int step;
node (){};
node(int num,int step){
this->step= step;
this->num=num;
}
};
void bfs(int n,int a,int b,node* floor){
int flag=0;
memset(vis,0,sizeof(vis));
queueque;
node st(a,0) ;
que.push(st);
while (!que.empty()){
node start = que.front();
que.pop();
vis[start.num]=1;
if(start.num==b) {
cout<=1&&num<=n&&!vis[num]) { que.push( node(num,start.step+1)); } } else{ int num = start.num+floor[start.num].num; if(num>=1&&num<=n&&!vis[num]) {
que.push(node(num,start.step+1));
}
}
}
}
if(!flag)cout<<"-1"<<endl;
}

int main(){
int n,a,b,k;
while (cin>>n,n>0){
cin>>a>>b;
node floor[210];
for (int i = 1; i <= n; i++){ cin>>k;
floor[i].num=k;
floor[i].step=0;
}
bfs(n,a,b,floor);
}
}

第二种解法:使用最短路dijkstra

#include
#include
#include
#include
#include
using namespace std;
const int N =205;
const int INF = 9999999;
int n;
int graph[N][N];
int dist[N];
bool vis[N];
void dijkstra(int s){
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++){ dist[i] = graph[s][i]; } for(int i=1;i<=n;i++){ int mindis = INF; int mark; for(int j=1;j<=n;j++){ if(!vis[j]&&dist[j]dist[mark]+graph[mark][j]){
dist[j] = dist[mark]+graph[mark][j];
}
}
}
}
int main(){
while(scanf("%d",&n)!=EOF,n){
int s,t;
scanf("%d%d",&s,&t);
for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) graph[i][j]=0; else graph[i][j] = INF; } } for(int i=1;i<=n;i++){ int num; scanf("%d",&num); if(i-num>=1) graph[i][i-num] = 1;
if(i+num<=n) graph[i][i+num] = 1; } dijkstra(s); if(dist[t]>=INF) printf("-1\n");
else printf("%d\n",dist[t]);
}
return 0;
}