POJ 3278 Catch that cow

深碍√TFBOYSˉ_ 2022-06-18 09:22 186阅读 0赞

> Catch That Cow  
> Time Limit: 2000MS Memory Limit: 65536K  
> Total Submissions: 87429 Accepted: 27431  
> 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

> 题意：在一个数轴上，有一个农民位于 n的位置处，有一头牛位于k 的位置处，农民 有三种走路方式：①若农民位于x ，农民可以移动一步到x+1 或x-1 ②若农民位 于x ，农民可以跳跃到2\*x 处。问：农民需要最少多少步抓住那头牛？

> 题解：从农民的起点开始BFS广搜，通过农民的三种 移动方式(x-1，x+1，2\*x)来向队列中插入节点，BFS广搜到牛的位置即可。

#include<iostream>
    #include<queue>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    
    const int maxn=100001;
    
    bool vis[maxn];//标记数组
    int step[maxn];//所走的步数
    queue <int> q;
    
    int bfs(int n,int k)
    {
        int head,next;
        q.push(n);   //开始在n位置，n入队
        step[n]=0;
        vis[n]=true; //标记
        while(!q.empty())  //当队列非空
        {
            head=q.front();  //取队首
            q.pop();         //弹出对首
            for(int i=0;i<3;i++)     //三种走法
            {
                if(i==0) next=head-1;
                else if(i==1) next=head+1;
                else next=head*2;
                if(next<0 || next>=maxn) continue; //剪枝
                if(!vis[next])  //如果next位置未被访问
                {
                    q.push(next);    //入队
                    step[next]=step[head]+1;  //步数+1
                    vis[next]=true;  //标记已访问
                }
                if(next==k) return step[next];  //遍历到结果，返回步数
            }
        }
    }
    int main()
    {
        int n,k;
        while(cin>>n>>k)
        {
            memset(step,0,sizeof(step));
            memset(vis,false,sizeof(vis));
    
            while(!q.empty()) q.pop(); 
            if(n>=k) cout<<n-k<<endl;
            else cout<<bfs(n,k)<<endl;
        }
        return 0;
    }