***参考Catch That Cow（BFS）

Catch That Cow

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 67   Accepted Submission(s) : 22

Problem 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

 

Source

PKU

 

 

题意：牛逃跑了，人要去抓回来这只牛，他们在一条直线上 ，现在牛的坐标是K，人的坐标是N，牛呆在原位置不动。人有两种行进方式，步行和传送，步行可以向前或向后走一步，传送为到达人当前坐标*2 的位置。每行进一次用一分钟，问人最少需要几分钟可以抓到牛。

 

思路：

 

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int maxn=;

 int vis[maxn+];

 int n,k;

 struct node

 {

     int x,c;

 };

 int BFS()

 {

     queue<node> q;

     while(!q.empty())

         q.pop();

     memset(vis,,sizeof(vis));

     node cur,next;

     cur.x=n,cur.c=;

     vis[cur.x]=;

     q.push(cur);

     while(!q.empty())

     {

         cur=q.front();

         q.pop();

         for(int i=; i<; i++)

         {

             if(i==)

                 next.x=cur.x-;

             else if(i==)

                 next.x=cur.x+;

             else

                 next.x=cur.x*;

             next.c=cur.c+;

             if(next.x==k)

                 return next.c;

             if(next.x>= && next.x<=maxn && !vis[next.x])

             {

                 vis[next.x]=;

                 q.push(next);

             }

         }

     }

     return ;

 }

 int main()

 {

     freopen("1.txt","r",stdin);

     while(~scanf("%d%d",&n,&k))

     {

         if(n>=k)

         {

             printf("%d\n",n-k);

             continue;

         }

         printf("%d\n",BFS());

     }

     return ;

 }