Catch That Cow（BFS）

电玩女神 2022-08-04 12:54 7阅读 0赞

Catch That Cow

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;62027</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;19403</td> 
  </tr> 
 </tbody> 
</table>

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

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

[USACO 2007 Open Silver][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    int vis[200005];
    int s,e;
    struct node
    {
        int cur;
        int step;
    };
    int check(node a)
    {
        if(a.cur>200005||a.cur<0||vis[a.cur])
        {
            return 0;
        }
        return 1;
    }
    int bfs(int p)
    {
        queue<node>Q;
        node rencent,next;
        rencent.cur=p;
        rencent.step=0;
        vis[rencent.cur]=1;
        Q.push(rencent);
        while(!Q.empty())
        {
            rencent=Q.front();
            Q.pop();
            if(rencent.cur==e)
            {
                return rencent.step;
            }
            next.cur=rencent.cur+1;
            if(check(next))
            {
                vis[next.cur]=1;
                next.step=rencent.step+1;
                Q.push(next);
            }
            next.cur=rencent.cur-1;
            if(check(next))
            {
                vis[next.cur]=1;
                next.step=rencent.step+1;
                Q.push(next);
            }
            next.cur=rencent.cur*2;
            if(check(next))
            {
                vis[next.cur]=1;
                next.step=rencent.step+1;
                Q.push(next);
            }
        }
    }
    int main()
    {
        while(cin>>s>>e)
        {
            memset(vis,0,sizeof(vis));
            cout<<bfs(s)<<endl;
        }
    }

[USACO 2007 Open Silver]: http://poj.org/searchproblem?field=source&key=USACO+2007+Open+Silver