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?
有人通知FJ他的逃跑的奶牛的位置，FJ要立即把它抓回来。他现在位于点N (0 ≤ N ≤ 100,000)，而奶牛位于跟他同一直线上的点K (0 ≤ K ≤ 100,000)。FJ有两种方法去抓住奶牛：走或传。
走：FJ能从点X走到X-1或X+1的位置，用时一分钟。
传：FJ能从点X到2*X的位置，用时一分钟。
如果奶牛在原地不动，问FJ至少要多少分钟才能抓住奶牛。
输入输出格式
输入格式：第一行，两个整数，N和K
输出格式：FJ抓住奶牛用的最少时间。
输入输出样例
输入样例#1：
5 17
输出样例#1：
4
说明
样例解释：
抓住奶牛最快的路径是5-10-9-18-17，用时4分钟。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstdlib>
using namespace std;
const int N=100010;
struct node{
int x,step;
}now,nxt,top;
int peo,milk;
bool vis[N];
queue<node>q;
inline int read()
{
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
inline void bfs(int start)
{
now.x=start;
now.step=0;
q.push(now);
while(!q.empty())
{
top=q.front();
q.pop();
int x=top.x;
if(x==milk)
{
printf("%d
",top.step);
exit(0);
}
if(x+1>=0&&x+1<=100000&&!vis[x+1])
{
vis[x+1]=1;
nxt.x=x+1;
nxt.step=top.step+1;
q.push(nxt);
}
if(x-1>=0&&x-1<=100000&&!vis[x-1])
{
vis[x-1]=1;
nxt.x=x-1;
nxt.step=top.step+1;
q.push(nxt);
}
if(x*2>=0&&x*2<=100000&&!vis[x*2])
{
vis[x*2]=1;
nxt.x=x*2;
nxt.step=top.step+1;
q.push(nxt);
}
}
}
int main()
{
peo=read();
milk=read();
bfs(peo);
return 0;
}