GroupBlog

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

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.

可以类比于最短路，用bfs在区间里进行遍历，不用回溯

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
//#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  long long ll;
typedef  unsigned long long  ull; 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}

typedef struct node{
	int x;
	int step;
}NODE;


int book[1000205];
int bfs();

ll re;
int n,k;
int main()
{
	ios::sync_with_stdio(false);
	while(cin >>n>>k)
	{
		re =9999999999;
		ll t=n;
		memset(book,0,sizeof(book));

		cout <<bfs()<<endl;
	}
	
} 



int  bfs()
{
	queue<NODE> Q;
	NODE tt;
	tt.x = n;
	tt.step = 0;
	book[n]++;
	Q.push(tt);
	ll ct =0;
	while(!Q.empty())
	{
		NODE cur = Q.front();
		if(cur.x==k)
			return cur.step;
		Q.pop();
		NODE t;
		int xx = cur.x+1;
		if(xx>=0&&xx<=100000&&book[xx]==0)
		{
			t.x = xx;
			book[xx]++;
			t.step = cur.step+1;
			Q.push(t);
		}
		xx  =  cur.x-1;
		if(xx>=0&&xx<=100000&&book[xx]==0)
		{
			t.x = xx;
			book[xx]++;
			t.step = cur.step+1;
			Q.push(t);
		}
		xx = cur.x*2;
		if(xx>=0&&xx<=100000&&book[xx]==0)
		{
			t.x = xx;
			book[xx]++;
			t.step = cur.step+1;
			Q.push(t);
		}
	
	}
}