POJ 3278 Catch That Cow (BFS)

POJ 3278 Catch That Cow (BFS)

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 minuteTeleporting: 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

题意

农夫需要找到他的牛，农夫现在所在位置是N，牛在K点，假设牛是不动的，农夫有三种走法：

向前走一步（N+1）向后走一步（N-1）跳到当前位置两倍处（2*N）

问，最少走多少次才能找到他的牛。

思路

简单的bfs，把农夫当前位置加入队列，然后出队判断每一个点，并模拟下一次的走法，注意的是，需要标记走过的点，否则会爆栈。

AC代码

#include #include#include#include#include#include#define MAXX 100005using namespace std;bool isvisted[MAXX];struct node{ int n; int time; node(int n,int time) { this->n=n; this->time=time; }};void bfs(int n,int k){ memset(isvisted,false,sizeof(isvisted)); node ans=node(n,0); isvisted[n]=true; queuesk; sk.push(ans); while(!sk.empty()) { node p=sk.front(); sk.pop(); isvisted[p.n]=true; //标记走过的点 if(p.n==k) //找到 { ans=p; break; } if(p.n+1=0&&!isvisted[p.n-1]) sk.push(node(p.n-1,p.time+1)); if(p.n*2

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。