简单BFS hdu 1548

这题是最简单最纯粹的bfs广搜，只要作一下标记去过的地方，不能再去，就OK啦! 

链接：

when you is on floor A,and you want to go to floor B,how many times at least he havt to
press the button "UP" or "DOWN"?

题意：一个特别的电梯，按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

 

充分利用flag[]数组来标记，所走过的步数

#include<iostream>
#include<queue>
using namespace std;

int N,A,B;
int floor[255],flag[255];

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+floor[t];//i,ki

        if(next>=1 && next<=B && flag[next]==0)//向上
        {
            q.push(next);
            flag[next]=flag[t]+1;
            //printf("%d",next);
        }

        next=t-floor[t];//i,ki
        if(next>=1 && next<=B && flag[next]==0)//向下
        {
            q.push(next);
            flag[next]=flag[t]+1;
            //printf("%d",next);
        }

    }
    if(t!=E)
        flag[B]=0;//匹配不成功
}
int main()
{
    while(scanf("%d",&N)&& N!=0)
    {
        scanf("%d %d",&A,&B);
            for(int i=1;i<=N;i++)
            {
                scanf("%d",&floor[i]);
            }
            memset(flag,0,sizeof(flag));
        BFS(A,B);
        printf("%d\n",flag[B]-1);//因为一开始将flag[A]=1
    }
    return 0;
}