ACM-BFS之A strange lift——hdu1548

3

开始一些BFS练习了，先来一道简单的，这是一栋大楼，有一部很奇怪的电梯，电梯只有两个按钮，

UP和DOWN，每个楼层有一个数字num，如果你在第2层，你按UP，电梯会到达 num+2层，按DOWN亦然，

到达2-num层，求一个人从一个楼层要去另一个楼层，需要按几步？

（这个电梯够让人捉急的！）

当然如果碰到0层或者-1层都不能到达，碰到大于刚开始的n层的也不能到达，

如果永远到不了需要去的那一层，就输出-1了。

广搜，队列做，标准的BFS题目呀，很容易就AC了。。

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
// st数组记录每个楼层能上行下行的数字，vis记录是否走过该楼层
int st[201],vis[201];
int start,finish,n;
// 该结构体记录到lift楼层用了几步
struct Elevator
{
    int lift,step;
}ele[201];

int bfs(void)
{
    Elevator t,k;
    queue <Elevator> q;
    memset(vis,0,sizeof(vis));

    // 第一个点入队列
    t.lift=start;
    t.step=0;
    vis[t.lift]=1;
    q.push(t);

    while(!q.empty())
    {
        t=q.front();
        q.pop();
        // 到达终点  直接返回步数
        if(t.lift==finish)  return t.step;

        // 从该楼层向下走
        k.lift=t.lift-st[t.lift];
        if(k.lift>0 && k.lift<=n && !vis[k.lift])
        {
            k.step=t.step+1;
            vis[t.lift]=1;
            q.push(k);
        }
        // 从该楼层向下走
        k.lift=t.lift+st[t.lift];
        if(k.lift>0 && k.lift<=n && !vis[k.lift])
        {
            vis[t.lift]=1;
            k.step=t.step+1;
            q.push(k);
        }
    }
    // 如果没有结果 -1
    return -1;
}

int main()
{
    int i;
    while(cin>>n)
    {
        if(!n)  break;

        cin>>start>>finish;
        for(i=1;i<=n;++i)   cin>>st[i];
        cout<<bfs()<<endl;
    }
    return 0;
}

ACM-BFS之A strange lift——hdu1548,布布扣,bubuko.com

ACM-BFS之A strange lift——hdu1548

原文：http://blog.csdn.net/lttree/article/details/22927131