Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 77420		Accepted: 24457

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.

Source

---

BFS

小优化：k<n直接n-k

注意边界处理，x<=k而不是x*2<=k，因为有时候还是要先两杯再往回走，比如n很靠前

////  main.cpp//  poj3278////  Created by Candy on 9/27/16.//  Copyright © 2016 Candy. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=2e5+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x;}int n,k,head=1,tail=0,ans=INF;struct data{    int x,d;    data(int a=0,int b=0):x(a),d(b){}}q[N];int vis[N];void bfs(){    q[++tail]=data(n,0);vis[n]=1;    while(head<=tail){        data now=q[head++];        int x=now.x,d=now.d;        if(x==k){printf("%d",d);return;}        if(x+1<=k&&!vis[x+1]){            vis[x+1]=1;            q[++tail]=data(x+1,d+1);        }        if(x-1>=0&&!vis[x-1]){            vis[x-1]=1;            q[++tail]=data(x-1,d+1);        }        if(x<=k&&!vis[x<<1]){            vis[x<<1]=1;            q[++tail]=data(x<<1,d+1);        }    }}int main(int argc, const char * argv[]) {    n=read();k=read();    if(k