Catch That Cow

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?

Line 1: Two space-separated integers: N and K

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

5 17

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.

teddy   |   We have carefully selected several similar problems for you:            

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int vis[200100];int n,m;struct node{ int first; int second; node(int a,int b) { first=a; second=b; }};void bfs(){ queue
          
            que; que.push(node (n,0)); vis[n]=1; int k,t; while(1) { node now=que.front(); que.pop(); k=now.first; t=now.second; if(k==m) { printf("%d\n",t); break; } if(!vis[k-1]&&k-1>=0) { vis[k-1]=1; que.push(node(k-1,t+1)); } if(!vis[k+1]&&k+1<=100000) { vis[k+1]=1; que.push(node(k+1,t+1)); } if(!vis[k*2]&&k*2<=100000) { vis[k*2]=1; que.push(node(k*2,t+1)); } }}int main(){ while(~scanf("%d%d",&n,&m)) { memset(vis,0,sizeof(vis)); bfs(); } return 0;}