最简单的bfs

93 阅读 0 评论 62 点赞

我是靠谱客的博主文艺龙猫，最近开发中收集的这篇文章主要介绍最简单的bfs，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意大意：

一个特别的电梯，按up可升上k[i]层，到大i+k[i]层，down则到达i-k[i]层，最高不能超过n，最低不能小于1，给你一个起点和终点，问最少可以按几次到达目的地。在一个N层高的楼有一个奇怪的电梯，在每一层只能上升或下降一个特定的层数，中间不会停止，在给定的条件下，问能不能到达指定楼层，可以到达的话返回转操作次数，不可以的话返回-1.

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".

N A B
Sample Input
5 1 5
3 3 1 2 5
0

Sample Output
3

ac代码：

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int floo[225],flag[225];
void bfs(int s,int e){
    queue<int>q;
    q.push(s);
    flag[s]=1;
    int t;
    while(!q.empty()){
        t=q.front();
        q.pop();
        if(t==e){
            break;
        }
        int next=t+floo[t];
        if(next>=1&&next<=b&&flag[next]==0){
            q.push(next);
            flag[next]=flag[t]+1;
        }
        next=t-floo[t];
        if(next>=1&&next<=b&&flag[next]==0){
            q.push(next);
            flag[next]=flag[t]+1;
        }
    }
    if(t!=e)
        flag[b]=0;
}
int main()
{
    int i;
    scanf("%d%d%d",&n,&a,&b);
    for(i=1;i<=n;i++){
        scanf("%d",&floo[i]);
    }
    memset(flag,0,sizeof(flag));
    bfs(a,b);
    printf("%dn",flag[b]-1);
    return 0;
}