博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ - 3278 Catch That Cow (BFS)
阅读量:4207 次
发布时间:2019-05-26

本文共 1470 字,大约阅读时间需要 4 分钟。

  在很久很久以前,有一位大师级程序员,实力高强,深不可测,代码能力无人能及。从来没有人听说过他的真名,只知道他在完成一段代码后,总会跟上一行注释“十四出品,必属精品”,于是他在编程江湖上便有了绰号“十四”。

  然而,十四大师并不满足于现有的一切,他想要让自己的实力有更进一步的提升。为此,他专程前往二次元世界修行。

  二次元旅程归来的十四大师学习了新的技能——闪现。

  在一条既定的直线道路上,“闪现”技能允许十四大师超时空移动。如果把道路视为一条数轴,使用闪现可以让十四大师瞬间移动到脚下坐标两倍的位置上。例如,如果十四大师站在坐标5的位置上,他可以直接闪现到坐标10的位置,如果继续闪现,则可以到达坐标20的位置上。

  现在十四大师打算练习一下“闪现”在生活中的应用。我们假定他站在坐标为a的位置上,而他想要到达坐标为b的位置(0 ≤a,b≤100000)。除了使用闪现外,他也可以像常人一样徒步向前或者向后走,而使用闪现视为行走了一步。请问十四大师最少需要走多少步才可以到达目标?

Input

  输入包含多组数据。每组数据占一行,包含两个整数a和b,表示十四大师的起始坐标和目的地坐标。(0 ≤a,b≤100000)

Output

  对于每组输入,输出一个整数,即十四大师到达目的地的最少步数。

Sample Input

5 17

Sample Output

4

Hint

  对于样例数据,最少步数的走法是:从坐标5闪现到坐标10,后退一步到坐标9,再闪现到坐标18,最后后退一步即到达坐标17。总共四步。

1.设置一个队列Q,从顶点出发,遍历该顶点后让其进队;

2.出队一个顶点元素,求该顶点的所有邻接点(对应于此题即FJ的三种走法),对于没有遍历过的邻接点遍历之,并 让其进队;

3.若队空停止,队不空时继续第2步

const int maxn=1e5+10;int n,k;int step[maxn],vis[maxn];queue
que;int bfs(int n,int k){ int now,nxt; step[n]=0; vis[n]=1; que.push(n); while(!que.empty()) { now=que.front(); que.pop(); for(int i=0;i<3;i++) { if(i==0)nxt=now-1; else if(i==1)nxt=now+1; else nxt=now<<1; if(nxt<0 || nxt>maxn) continue; if(!vis[nxt]) { vis[nxt]=1; que.push(nxt); step[nxt]=step[now]+1; } if(nxt==k) return step[nxt]; } } return 0;}int main(){ ios::sync_with_stdio(false); cin>>n>>k; if(n>=k)cout<
<

转载地址:http://xeali.baihongyu.com/

你可能感兴趣的文章
小练习 - 基于链表的栈和队列
查看>>
理论不扎实,编程不会有自己的想法
查看>>
数据库-子查询《mysql子查询的弱点》
查看>>
关于Synchornized,Lock,AtomicBoolean和volatile
查看>>
Private Members In JavaScript(javascript的私有成员)——翻译
查看>>
mvc——web和android
查看>>
数据库的commit以及rollback
查看>>
动态加载JS脚本的4种方法
查看>>
《MySQL必知必会》——MySQL管理事务处理
查看>>
《MySQL必知必会》——笔记
查看>>
《Spring揭秘》——AOP(笔记)
查看>>
《TCP/IP详解卷3》——HTTP(笔记)
查看>>
JVM——main()方法的执行。
查看>>
观止——《从Decorator,Adapter模式看Java/IO库》
查看>>
《Erlang程序设计》——笔记
查看>>
Erlang开发环境Windows+Emacs+Distel配置
查看>>
Erlang的特点——小结
查看>>
Erlang的makefile——小例子
查看>>
蜗牛爬井——Erlang版本
查看>>
《Erlang程序设计》第8章习题解
查看>>