Hunter'sBlog

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?

看不懂吗翻译

大意如下
农夫想要抓住一头牛 他站在一个地方 牛在一个地方，农夫可以消耗一点体力从当前坐标$X$走到$X+1$,$X-1$或者$X*2$的地方
请问最少多少体力能够抓到牛

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

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}

完事儿~

评论