Yui的狗窝
Yui的狗窝
hdoj 1548 A strange lift bfs

原题:http://acm.hdu.edu.cn/showproblem.php?pid=1548

普通的求最短路径的题目,bfs即可,随手练练。

#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
bool vis[201];
int N,b,e,res,k[201];
struct point
{
    int x,time;
};
bool check(int a)
{
    if(a>=1&&a<=N)
        if(!vis[a])
            return true;
    return false;
}
bool bfs()
{
    queue<point> q;
    point cur,next;
    cur.x=b;cur.time=0;
    q.push(cur);
    vis[cur.x]=true;
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(cur.x==e)
        {
            res=cur.time;
            return true;
        }
        next.x=cur.x+k[cur.x];
        next.time=cur.time+1;
        if(check(next.x))
        {
            q.push(next);
            vis[next.x]=true;
        }
        next.x=cur.x-k[cur.x];
        if(check(next.x))
        {
            q.push(next);
            vis[next.x]=true;
        }
    }
    return false;
}
int main()
{
    while(cin>>N,N)
    {
        memset(vis,false,sizeof(vis));
        cin>>b>>e;
        for(int i=1;i<=N;i++)
            cin>>k[i];
        if(bfs())
            cout<<res<<endl;
        else
            cout<<-1<<endl;
    }
}
没有标签
首页      算法训练      hdoj 1548 A strange lift bfs
https://secure.gravatar.com/avatar/d0fe7f1b17d5e9122db921e3a8cc327f?s=256&d=mm&r=g

Suzumiya, Yui

文章作者

发表评论

textsms
account_circle
email

Yui的狗窝

hdoj 1548 A strange lift bfs
原题:http://acm.hdu.edu.cn/showproblem.php?pid=1548 普通的求最短路径的题目,bfs即可,随手练练。 #include<iostream> #include<algorithm> #include<queue> #inc…
扫描二维码继续阅读
2017-07-16


没有激活的小工具