B - Catch That Cow

    抓牛问题,一开始使用了回溯法递归,然后就Time Limit Exceeded了,于是乎,用上了队列,然后上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 - 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?

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.




下面贴出我的代码并给予解释:


#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
const int maxn=100000+10;
class Point{            //定义一个记录位置的类
public:
    int local;          //当前坐标
    int step;           //当前步数
};
int farmer, cow, result;       //农夫和牛的位置,答案
bool line[maxn];               //记录位置是否走过的数组
queue<Point> orgin;            //搜索的队列
void Init()
{
    //初始化操作,将地图线全部设置为没有走,并且清空列队
    memset(line, 0, sizeof(line));
    while(!orgin.empty())orgin.pop();
    result = 0;
}
int check(int x)
{
    return (x<0||x>100000||line[x])?0:1;       //判断是否可以走
}
void Bfs(int now)
{
    Point point, next;    //实例化两个对象,一个当前对象,一个下一个对象,对象,对象,对象,,,
    point.local=now;
    point.step=0;
    line[now]=true;
    orgin.push(point);    //将第一个位置处理好之后扔到队列里面去
    while(!orgin.empty())
    {
        point = orgin.front();    //拿一个位置出来,搜他
        orgin.pop();
        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; //两倍搜索
            if(check(next.local))
            {
                //如果可以搜,那就搜呗
                next.step = point.step+1;
                line[next.local]=true;
                orgin.push(next);
            }
        }
    }
}
int main()
{
    while(cin>>farmer>>cow)
    {
        Init();
        Bfs(farmer);
        cout<<result<<endl;
    }
    return 0;
}