题解报告:hdu 2717 Catch That Cow(bfs)
2024-08-26 09:52:46
Problem Description
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?
* 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?
Input
Line 1: Two space-separated integers: N and K
Output
Line 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.
解题思路:典型的bfs求最少时间。记录每个位置是否被访问,并且用一个结构体来标记每个从初始位置到达某个正访问的位置(之前为未访问)所花费的时间,有三次操作,每次操作都必须在原来的位置上进行位置转移,详解看代码。
AC代码:
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int maxn=1e5+;
int n,k,cnt;bool vis[maxn];//标记是否访问
struct node{int x,step;}nod;//标记达到当前位置的步数
queue<node> que;
void bfs(int x){
while(!que.empty())que.pop();//清空
memset(vis,false,sizeof(vis));
nod.x=n,nod.step=;vis[x]=true;//同时将初始位置x标记为true
que.push(nod);//先将初始位置入队
while(!que.empty()){
nod=que.front();que.pop();
if(nod.x==k){cout<<nod.step<<endl;return;}//这一步不能忘记,不然会出错,如果当前节点的值和k相等,则直接返回所花费的时间为0
for(int i=;i<;++i){//遍历三次操作,查看是否还有可以到达的地方
node next=nod;//每一次操作都从原来那个位置到另一个位置
if(i==)next.x-=;
else if(i==)next.x+=;
else next.x*=;
next.step++;//到达对应位置的时间在原来的基础上加1
if(next.x==k){cout<<next.step<<endl;return;}//如果到达终点,则直接返回所花费的时间
if(next.x>=&&next.x<maxn&&!vis[next.x]){//如果下一个位置在0~10^5范围内,并且还未访问,就可以将其入队
vis[next.x]=true;//将其标记为已访问状态
que.push(next);//将下一个位置入队
}
}
}
}
int main(){
while(cin>>n>>k){bfs(n);}
return ;
}
最新文章
- Tiny6410 LCD设置
- Mesa 3D
- JS 模板引擎之JST模板
- 标识映射(Identify Map)
- Mysql单实例脚本自动化安装
- String Subtraction
- android学习日记04--开发中的通用细节
- Opencv2.4.4作图像旋转和缩放
- CenOS下安装Eclipse并配置PyDev
- 聊聊Node.js 独立日漏洞
- jquery模板下载网站
- PHP生成验证码
- FMDB的简单实用
- AltiumDesigner印制导线的走向及形状
- php 安装xdebug进行调试(phpstorm)
- mysql查询INFORMATION_SCHEMA表很慢的性能优化
- Codeforces 1077 F2 - Pictures with Kittens (hard version)
- C#获取网页的HTML码、下载网站图片
- 在java中(==)的用法
- Day1-Python基础--数据类型
热门文章
- 【ZJOI2017 Round1练习&;BZOJ4773】D3T1 cycle(最小负环,倍增)
- 莫比乌斯反演套路二--(n/d)(m/d)给提出来--BZOJ3529: [Sdoi2014]数表
- EditText隐藏和显示
- jquery判断单选按钮radio是否选中的方法
- Django学习系列之captcha 验证码插件
- Centos7最小安装下Install Clamav(2017-06-09最后更新)
- POJ2155 Matrix 【二维树状数组】+【段更新点查询】
- node+vue-cli+webpack搭建教程
- Android Api Demos登顶之路(四十五)Loader--&;gt;Cursor
- chosen.jquery.js 搜索框只能从头匹配的解决思路+方法