空间最短路径，BFS(POJ3278)

悠悠 2022-01-09 08:49 311阅读 0赞

题目链接：[http://poj.org/problem?id=3278][http_poj.org_problem_id_3278]

#include <cstdio>
    #include <queue>
    #include <string.h>
    
    using namespace std;
    
    #define MAXN 200000
    
    int key[MAXN];///走到key[i]的步数
    bool vis[MAXN];///是否走过
    
    int bfs(int first,int last)
    {
        int v;
        queue<int>q;
    
        ///初始化没有走过
        memset(vis,false,sizeof(vis));
    
        q.push(first);
        key[first]=0;
        vis[first]=true;
    
        while(!q.empty())
        {
            v=q.front();
    
            q.pop();
    
            if(v==last)
                return key[v];
    
            ///向左走
            if((v-1)>=0&&(v-1)<MAXN&&!vis[v-1])
            {
                key[v-1]=key[v]+1;
                vis[v-1]=true;
                q.push(v-1);
            }
    
            ///向右走
            if((v+1)>=0&&(v+1)<MAXN&&!vis[v+1])
            {
                key[v+1]=key[v]+1;
                vis[v+1]=true;
                q.push(v+1);
            }
    
            ///跳
            if((v*2)>=0&&(v*2)<MAXN&&!vis[v*2])
            {
                key[v*2]=key[v]+1;
                vis[v*2]=true;
                q.push(v*2);
            }
        }
    }
    
    int main()
    {
        int n,k;
        while(scanf("%d%d",&n,&k)!=EOF)
        {
            printf("%d\n",bfs(n,k));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/TreeDream/p/5365741.html

[http_poj.org_problem_id_3278]: http://poj.org/problem?id=3278

发表评论取消回复

表情：

评论列表（有 0 条评论，311人围观）

还没有评论，来说两句吧...

相关阅读

相关蜂窝空间两点最短路径的Python实现

昨天和Mcree来一场痛快淋漓的头脑风暴！叶子为什么是绿色的? 聊起一步步到物理是如何接过生物学家的接力棒深入探索：参考链接：为什么植物是绿色的？为了减少光合作用中的噪音

﹏ヽ暗。殇╰゛Y/ 2024年03月22日 19:22/ 0 赞/ 19 阅读

相关最短路径

最短路径 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 YY 并不是把东西直接搬到

比眉伴天荒/ 2022年08月18日 02:28/ 0 赞/ 199 阅读

相关最短路径

\[hdu 2544\] ([http://acm.hdu.edu.cn/showproblem.php?pid=2544][http_acm.hdu.edu.cn_showp

r囧r小猫/ 2022年08月04日 08:27/ 0 赞/ 214 阅读

相关最短路径问题（最短路径）

最短路径问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

Love The Way You Lie/ 2022年08月01日 14:48/ 0 赞/ 278 阅读

相关最短路（最短路径）

最短路 Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other

缺乏、安全感/ 2022年08月01日 13:59/ 0 赞/ 208 阅读

相关最短路径

最短路径的迪杰斯特拉算法跟最小生成树的普利姆算法很像！但是这里的像只是代码相似，实质是不一样的！普利姆算法是从任意点开始，找到跟他最近的点记录距离，然后

比眉伴天荒/ 2022年08月01日 13:59/ 0 赞/ 209 阅读

相关最短路径

Problem Description 为了准备一年一度的校赛，大家都在忙着往赛场搬运东西，比如气球什么的。这时YY 也没有闲着，他也加入了搬运工的行列。已知学校有N 个

客官°小女子只卖身不卖艺/ 2022年07月12日 08:26/ 0 赞/ 237 阅读

相关最短路径问题

[sdut原题链接][sdut] 最短路径问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description

ゞ浴缸里的玫瑰/ 2022年07月10日 16:29/ 0 赞/ 254 阅读

相关最短路径

floyd算法最简单的最短路径算法，可以计算图中任意两点间的最短路径 folyd算法的时间复杂度是O(N3),如果是一个没有边权的图，把相连的两点间的距离设为dis

系统管理员/ 2022年06月11日 04:53/ 0 赞/ 260 阅读

相关空间最短路径，BFS(POJ3278)

题目链接：[http://poj.org/problem?id=3278][http_poj.org_problem_id_3278] include <cstdio

悠悠/ 2022年01月09日 08:49/ 0 赞/ 312 阅读