[kuangbin带你飞]专题一简单搜索 C

ゝ一世哀愁。 2023-08-17 15:40 43阅读 0赞

# C - Catch That Cow #

题目链接：[https://vjudge.net/contest/65959\#problem/C][https_vjudge.net_contest_65959_problem_C]

题目：

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点（0≤N≤100,000）开始，并且母牛在同一数字线上的点K（0≤K≤100,000）。 农夫约翰有两种交通方式：步行和传送。 *步行：FJ可以在一分钟内从任何一点X移动到X - 1或X + 1点 *传送：FJ可以在一分钟内从任意点X移动到2×X点。 如果母牛不知道它的追求，根本不动，那么农夫约翰需要多长时间才能找回它？ 输入 第1行：两个以空格分隔的整数：N和K. 产量 第1行：Farmer John捕捉逃亡牛所需的最短时间（以分钟为单位）。
    思路：广搜

#include<iostream>
    #include<queue>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    bool book[maxn];
    int fan[maxn];
    queue<int>qu;
    int bfs(int N,int K)
    {
        int tou,xia;//tou是现在位置，xia是下一步的位置
        qu.push(N);//把现在位置压入队列中，
        fan[N]=0;//一开始步数为0
        book[N]=true;//该位置已经被走过了
        while(!qu.empty())
        {
            tou=qu.front();//将现在的位置存入队列中
            qu.pop();//删去队首
            //cout<<qu.size()<<endl;
            for(int i=0;i<3;i++)//三个操作
            {
                if(xia==K)
                {
                    return fan[xia];
                }
                if(i==0)
                    xia=tou-1;
                else if(i==1)
                    xia=tou+1;
                else
                    xia=tou*2;
                if(xia<0||xia>100000)//防止越界
                    continue;
                if(!book[xia])
                {
                    qu.push(xia);//把下一步的位置存入队列中
                    fan[xia]=fan[tou]+1;
                    book[xia]=true;//已经走过
                }
            }
        }
        return fan[xia];
    }
    int main()
    {
        int N,K;
        while(cin>>N>>K){
        memset(fan,0,sizeof(fan));
        memset(book,false,sizeof(book));
        while(!qu.empty())
        {
            qu.pop();
        }
        cout<<bfs(N,K)<<endl;
    }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11143182.html

[https_vjudge.net_contest_65959_problem_C]: https://vjudge.net/contest/65959#problem/C