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

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

 

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting. 
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute 
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute. 
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

InputLine 1: Two space-separated integers: N and KOutputLine 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
#include 
#include
#include
using namespace std;const int N = 1000000;int map[N+10];int n,k;struct node{ int x,step;};int check(int x){ if(x<0 || x>=N || map[x]) return 0; return 1;}int bfs(int x){ int i; queue
Q; node a,next; a.x = x; a.step = 0; map[x] = 1; Q.push(a); while(!Q.empty()) { a = Q.front(); Q.pop(); if(a.x == k) return a.step; next = a; next.x = a.x+1; if(check(next.x)) { next.step = a.step+1; map[next.x] = 1; Q.push(next); } next.x = a.x-1; if(check(next.x)) { next.step = a.step+1; map[next.x] = 1; Q.push(next); } next.x = a.x*2; if(check(next.x)) { next.step = a.step+1; map[next.x] = 1; Q.push(next); } } return -1;}int main(){ int ans; while(~scanf("%d%d",&n,&k)) { memset(map,0,sizeof(map)); ans = bfs(n); printf("%d\n",ans); } return 0;}

 

转载于:https://www.cnblogs.com/edych/p/7237679.html

你可能感兴趣的文章
猴子数据教你如何快速查询域名备案是否存在
查看>>
【跃迁之路】【735天】程序员高效学习方法论探索系列(实验阶段492-2019.2.25)...
查看>>
小程序红包雨
查看>>
开年巨制!千人千面回放技术让你“看到”Flutter用户侧问题
查看>>
第十二课时:渲染函数和JSX快速掌握
查看>>
Visio替代图表工具 - 为什么Visual Paradigm Online?
查看>>
市场变冷,不要灰心。更应该延长你的黄金岁月
查看>>
微服务之数据同步Porter
查看>>
从前端程序员的视角看小程序的稳定性保障
查看>>
Flutter 1.2 发布,添加应用内支付和 App Bundles
查看>>
docker笔记2-镜像与容器
查看>>
如何使用less实现随机下雪动画详解
查看>>
完成端口服务器模型
查看>>
python 图像处理:一福变五福
查看>>
el-dialog 模态框拖拽
查看>>
教你React Native使用fetch实现图片上传
查看>>
Linux php7.0安装phpredis
查看>>
彻底弄懂 JavaScript 执行机制
查看>>
另类爬虫:从PDF文件中爬取表格数据
查看>>
React.memo
查看>>