Catch That Cow

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9753    Accepted Submission(s): 3054

Problem DescriptionFarmer 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?

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

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

Sample Input5 17 

Sample Output4 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.

SourceUSACO 2007 Open Silver 

Recommendteddy   |   We have carefully selected several similar problems for you:  1372 1072 1180 1728 1254   一道很简单的一维广搜题，将每次坐标变化存入队列，标记不重复即可。 题意：一个农民去抓一头牛，输入分别为农民和牛的坐标，农民每次的移动可以坐标+1，或者坐标-1，或者坐标乘2三种变化，假设牛不知道农民来抓它而一直呆在原地不动，农民最少需要几步才能抓到牛。 附上代码：

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <queue>
 #define M 100005
 using namespace std;
 int n,m;
 int visit[M];    //标记数组，0表示没走过，1表示已走过
 struct node
 {
     int x,t;
 } s1,s2;
 void BFS()
 {
     queue<node> q;
     while(!q.empty())
         q.pop();
     s1.x=n;
     s1.t=;
     visit[n]=;     //农民起始位置标记为已走过
     q.push(s1);
     while(!q.empty())
     {
         s1=q.front();
         q.pop();
         if(s1.x==m)   //结束标志为农民到了牛的位置
         {
             printf("%d\n",s1.t);
             return;
         }
         s2.x=s1.x+;      //坐标+1
         if(s2.x>=&&s2.x<=M&&!visit[s2.x])  //判断变化后的数字是否超过了范围
         {
             visit[s2.x]=;
             s2.t=s1.t+;
             q.push(s2);
         }
         s2.x=s1.x-;      //坐标-1
         if(s2.x>=&&s2.x<=M&&!visit[s2.x])
         {
             visit[s2.x]=;
             s2.t=s1.t+;
             q.push(s2);
         }
         s2.x=s1.x*;      //坐标*2
         if(s2.x>=&&s2.x<=M&&!visit[s2.x])
         {
             visit[s2.x]=;
             s2.t=s1.t+;
             q.push(s2);
         }
     }
 }
 int main()
 {
     int i,j;
     while(~scanf("%d %d",&n,&m))
     {
         memset(visit,,sizeof(visit));    //开始全部定义为0
         BFS();
     }
     return ;
 }