POJ-3278题解

POJ-3278

题目描述

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

解题思路

使用广度优先搜索，将当前的位置X所能到达的地方的坐标放入队列，并将当前的坐标从队列中删除，知道队列为空，典型的BFS

代码如下

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int ans[100005],n,k;
queue <int> q;

int bfs()
{
    if (n==k) return 0;
    while (!q.empty()) q.pop();
    q.push(n);
    while (q.size())
    {
        int tmp=q.front();
        //cout<<"tmp="<<tmp<<endl;
        q.pop();
        if (tmp-1>=0 && tmp-1<=100000 && ans[tmp-1]==-1)
        {
            if (tmp-1==k) return ans[tmp]+1;
            q.push(tmp-1);
            ans[tmp-1]=ans[tmp]+1;
        }
        if (tmp+1>=0 && tmp+1<=100000 && ans[tmp+1]==-1)
        {
            if (tmp+1==k) return ans[tmp]+1;
            q.push(tmp+1);
            ans[tmp+1]=ans[tmp]+1;
        }
        if (tmp*2>=0 && tmp*2<=100000 && ans[tmp*2]==-1)
        {
            if (tmp*2==k) return ans[tmp]+1;
            q.push(tmp*2);
            ans[tmp*2]=ans[tmp]+1;
        }
    }
}

int main()
{
    cin>>n>>k;
    memset(ans,-1,sizeof(ans));
    ans[n]=0;
    cout<<bfs();
    //for (int i=1;i<=20;i++)
    //    cout<<ans[i]<<" ";
    return 0;
}

完事儿~~~~