Description
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 <iostream> #include<vector> #include<bits/stdc++.h> #include<queue> 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)); queue<node>que; 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<<start.step<<endl; return; } for (int i = 0; i < 2; i++){ if(i==0){ int num = start.num-floor[start.num].num; if(num>=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 <stdio.h> #include <algorithm> #include <cstring> #include <cmath> #include <queue> 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]<mindis){ mark = j; mindis = dist[j]; } } vis[mark] = true; 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; }
原文：https://www.cnblogs.com/BlairGrowing/p/14314801.html
