一个电梯有n层，每一层有一个数k[i],和2个按钮，UP和DOWN，表示从这一层可以到达i+k[i] 或i-k[i] .

给出a,b,问从a到b 最少需要按多少下按钮。

直接bfs.

 

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=210; 6 int n,a,b; 7 int k[maxn]; 8 bool vis[maxn]; 9 int time[maxn];10 int bfs()11 {12     memset(vis,false,sizeof(vis));13     queue
         
          que;14     while(!que.empty())15         que.pop();16     que.push(a);17     vis[a]=true;18     time[a]=0;19     while(!que.empty())20     {21         int u=que.front();22         que.pop();23         if(u==b)24             return time[b];25         if(u-k[u]>0&&!vis[u-k[u]])26         {27             que.push(u-k[u]);28             vis[u-k[u]]=true;29             time[u-k[u]]=time[u]+1;30         }31         if(u+k[u]<=n&&!vis[u+k[u]])32         {33             que.push(u+k[u]);34             vis[u+k[u]]=true;35             time[u+k[u]]=time[u]+1;36         }37     }38     return -1;39 }40 int main()41 {42     while(scanf("%d%d%d",&n,&a,&b))43     {44         if(!n)45             break;46         for(int i=1;i<=n;i++)47             scanf("%d",&k[i]);48         int ans=bfs();49         printf("%d\n",ans);50     }51     return 0;52 }