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 ", bfs(n, m)); return 0; }