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≤100000)N (0 ≤ N ≤ 100000) on a number line and the cow is at a point K(0≤K≤100000)K (0 ≤ K ≤ 100000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  • Walking: FJ can move from any point XX to the points X−1X - 1 or X+1X + 1 in a single minute
  • Teleporting: FJ can move from any point XX to the point 2X2X 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: NN and KK

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.

Translation

农夫丢了奶牛，要去找奶牛。农夫和奶牛在一条数轴上，奶牛不动，农夫位于xx点，有三种走法（根据题意），每走一步花费一分钟，问至少花费几分钟找到奶牛。

Idea

由于每一种走法花费的时间都是相同的，可以采用BFSBFS的方法。
坑点是需要特判，如果n==kn==k，就要输出00。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<queue>
#include<iostream>
using namespace std;
const int N=100000;
bool vis[N+5];
int n,k;
struct state
{
	int x,step;
};
queue<state>q;
void bfs()
{
	vis[n]=1;
	state start;
	start.step=0;
	start.x=n;
	q.push(start);
	while(!q.empty())
	{
		int i;
		state now;
		state nxt;
		now=q.front();
		for(i=1;i<=3;i++)//枚举三种走法
		{
			if(i==1) nxt.x=now.x-1;
			else if(i==2) nxt.x=now.x+1;
			else nxt.x=now.x*2;
			nxt.step=now.step+1;
			if(nxt.x<0||nxt.x>N) continue;
			else if(vis[nxt.x]) continue;
			else
			{
				vis[nxt.x]=1;
				if(nxt.x==k)
				{
					cout<<nxt.step;
					return;
				}
				else q.push(nxt);
			}
		}
		q.pop();//出队
	}
}
void solve()
{
	cin>>n>>k;
	if(n==k) cout<<0;//特判
	else bfs();
}
int main()
{
	solve();
	return 0;
}