POJ 3278 Catch That Cow（赶牛行动）

POJ 3278 Catch That Cow（赶牛行动）

Time Limit: 1000MS    Memory Limit: 65536K

 

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?

农夫John被告知有奶牛企图逃跑欲火速擒回。他的初始位置为某条线的N (0 ≤ N ≤ 100,000)点，且奶牛在同一条线上的点K (0 ≤ K ≤ 100,000)。农夫John有两种移动方式：要么走路，要么传送。

* 走路: FJ可以从任意的点X用一分钟移动到 X - 1 或 X + 1
* 传送: FJ可以从任意的点X用一分钟传送到2 × X

如果牛完全不动，农夫John需要多少时间才能追回它们？

Input - 输入

Line 1: Two space-separated integers: N and K

1行：两个由空格分隔的整数：N和K

Output - 输出

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

1行：最短时间，表示农夫John需要多少分钟追回逃跑的奶牛。

Sample Input - 输入样例

5 17

 

Sample Output - 输出样例

4

 

题解

　　判断好条件，开辟两倍的空间（*2），直接SPFA（BFS）。

 

代码 C++

#include <cstdio>
#include <cstring>
#include <queue>
int data[200005];
int main(){
    int n, k, now, nxt, i, j;
    scanf("%d%d", &n, &k);
    k <<= 1;
    memset(data, 0x7F, sizeof data); data[n] = 0;
    std::queue<int>q; q.push(n);
    while (!q.empty()){
        now = q.front(); q.pop();
        j = now == 0 ? 1 : 3;
        for (i = 0; i < j; ++i){
            switch (i){
            case 0:nxt = now + 1; break;
            case 1:nxt = now << 1; break;
            case 2:nxt = now - 1; break;
            }
            if (i<2 && nxt > k) continue;
            if (data[nxt] > data[now] + 1){
                data[nxt] = data[now] + 1; q.push(nxt);
            }
        }
    }
    printf("%d
", data[k >> 1]);
    return 0;
}