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.
需求：有一个人现在的位置为n，有头牛现在的位置为k，
这个人从位置n开始走，有两三种走法，前进一步，后退一步，或者跳到2*n，所需的时间都是1
假设这头牛位置不变，问这个人追到这头牛所需的时间是多少
vis[i] = 0表示位置i没有走过，vis[i] =1表示位置i已经走过了
step[i]表示到达位置i所需要的部数
思路：宽度搜索，每步所有的走法按照特定的顺序依次入栈，先走到k所需的步数一定是最小的
第一步位置：n
第二步可能的位置：n+1, n-1, n*2;
每次的位置x必须满足 0<= x <= 100000;
按照可能的位置把所有的可能位置依次入栈（同时把这个位置标记为已经走过的），每次弹出栈顶元素，看从这个栈顶位置往下走每一步可能的位置，按照同样的方法把这些位置入栈
如果到达位置k，那么step[k]就是到达k所需的最小步数。
#include <cstdio>
#include <queue>
#define MAX 100001
using namespace std;
int n, m;
int ret[MAX], vis[MAX] = {0};
queue<int> q;
int bfs(int n, int m)
{
if(n == m)
return 0;
int cur;
q.push(n);
while(!q.empty())
{
cur = q.front();
q.pop();
if(cur + 1 < MAX && !vis[cur+1])
{
ret[cur+1] = ret[cur] + 1;
vis[cur+1] = 1;
q.push(cur+1);
}
if(cur + 1 == m)
break;
if(cur - 1 >= 0 && !vis[cur-1])
{
ret[cur-1] = ret[cur]+1;
vis[cur-1] = 1;
q.push(cur-1);
}
if(cur - 1 == m)
break;
if(cur * 2 < MAX && !vis[cur*2])
{
ret[cur*2] = ret[cur] + 1;
vis[cur*2] = 1;
q.push(cur*2);
}
if(cur * 2 == m)
break;
}
return ret[m];
}
int main()
{
scanf("%d%d", &n, &m);
printf("%d\n", bfs(n, m));
return 0;
}