B - Catch That Cow

    抓牛问题,一开始使用了回溯法递归,然后就Time Limit Exceeded了,于是乎,用上了队列,然后上bfs,左边搜,右搜,两倍传送再搜一波,瞬间秒杀,妈妈再也不用担心我会超时,哈哈哈哈....


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 - 1 or + 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?


Line 1: Two space-separated integers: N and K


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



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 <iostream>
#include <queue>
#include <memory.h>
using namespace std;
const int maxn=100000+10;
class Point{            //定义一个记录位置的类
    int local;          //当前坐标
    int step;           //当前步数
int farmer, cow, result;       //农夫和牛的位置,答案
bool line[maxn];               //记录位置是否走过的数组
queue<Point> orgin;            //搜索的队列
void Init()
    memset(line, 0, sizeof(line));
    result = 0;
int check(int x)
    return (x<0||x>100000||line[x])?0:1;       //判断是否可以走
void Bfs(int now)
    Point point, next;    //实例化两个对象,一个当前对象,一个下一个对象,对象,对象,对象,,,
    orgin.push(point);    //将第一个位置处理好之后扔到队列里面去
        point = orgin.front();    //拿一个位置出来,搜他
        if(point.local==cow){result=point.step;break;}  //如果找到牛,退出循环之后输出答案。
        next = point;
        for(int y=1;y<=3;y++)
            if(y==1)next.local = point.local+1; //前进一步搜索
            if(y==2)next.local = point.local-1; //后退一步搜索
            if(y==3)next.local = point.local*2; //两倍搜索
                next.step = point.step+1;
int main()
    return 0;