HDU 1548 A strange lift（bfs）

冷不防 2022-08-02 04:41 29阅读 0赞

最近在搞搜索算法

刚开始起步

要从基础开始额

各处找水题

偶然发现此题不错

做起来很有感觉  =\_=

题意是一个电梯

然后&\*%￥%\#@！%&\*%￥

呵呵哒，英语渣

从输入数据开始说吧

n层楼里有个电梯，每层电梯只能上升fi层或者下降fi层

现在你在a层，你想去b层，问需要按电梯几次

不少人是用最短路做的

可这不是赤裸裸的广搜吗 =\_=

code：

#include<stdio.h>
    #include<string.h>
    #include<queue>
    using namespace std;
    int floor[201],flag[201];
    int a,b;
    void bfs(int start,int end)
    {
        queue<int> q;
        q.push(start);
        int t;
        while(!q.empty())
        {
            t=q.fronr();
            q.pop();
            if(t==end)
                break;
            int next=t+floor[t];<span style="white-space:pre">			</span>//上升，next为上升后所在第几层
            if(next>=1&&next<=end&&flag[next]==0)
            {
                q.push(next);
                flag[next]=flag[t]+1;
            }
            next=t-floot[t];<span style="white-space:pre">			</span>//下降，next为下降后所在第几层
            if(next>=1&&next<=end&&flag[next]==0)
            {
                q.push(next);
                flag[next]=flag[t]+1;
            }
        }
        if(t!=end)
            flag[b]=-1;
    }
    int main()
    {
        int n,i;
        while(scanf("%d",&n),n)
        {
            scanf("%d %d",&a,&b);
            for(i=1;i<=n;i++)
                scanf("%d",&floor[i]);
            memset(flag,0,sizeof(flag));
            bfs(a,b);
            printf("%d\n",flag[b]);
        }
        return 0;
    }

我也是受一个大神启发，flag的作用不只是标记，还记录当前的操作次数

还要注意当不能从a到b的时候要输出-1

每学习一个算法，都对我有很大启发

惊叹原来还可以这样

怀中敬佩之情去钻研一个个算法

乐在其中