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?

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.

　　　　这道题是典型的宽搜ＢＦＳ，题意大概是Farmer John要抓奶牛。
　　　　Farmer John只有一下三种移动方式：
　　　　　　　　

1. 向前走一步，耗时一分钟。
2. 向后走一步，耗时一分钟。

3. 向前移动到当前位置的两倍N*2，耗时一分钟。

   　奶牛是不会动的。

通过分析可知，当奶牛在Farmer John后面时（即n >= k），Farmer John只能一步一步往回走，此时步数step = n - k.

其他情况则通过宽搜求结果。

根据宽搜的性质，所求得的结果必然是最优解。

代码如下：

#include<cstdio>
#include<queue>
#include<cstring>

const int MAX = 100000 + 5;
int n = 0, k = 0;
int step[MAX];
bool book[MAX];

bool ok(int x)//检查是否越界
{
    if (x < 0 || x > MAX - 5)
        return false;
    return true;
}

void check(int next, int last, std::queue<int>&q)//模拟走路的方式
{
    if (ok(next) && !book[next]) {
        step[next] = step[last] + 1;
        q.push(next);
        book[next] = true;
    }
}

void BFS()
{
    int last = 0, next = 0;
    std::queue<int> q;
    book[n] = true;
    step[n] = 0;
    q.push(n);
    while (!q.empty()) {
        last = q.front();
        q.pop();
        if (last == k) printf("%d\n", step[last]);
        next = last - 1;
        check(next, last, q);
        next = last + 1;
        check(next, last, q);
        next = last * 2;
        check(next, last, q);
    }

}

int main()
{
    while (scanf("%d%d", &n, &k) == 2) {
        memset(book, false, sizeof book);
        memset(step, 0, sizeof book);
        if (k <= n) printf("%d\n", n - k);
        else BFS();
    }
    return 0;
}

刚开始时，在ok函数中，我写成if (x < 0 || x >＝ MAX - 5)　结果wrong answer　了。尴尬。被边界数据阴了。。。。。所以是不需要等号的。因为测试的数据中最大刚好有个１０００００。