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 ( ≤ N ≤ ,)点，且奶牛在同一条线上的点K ( ≤ K ≤ ,)。农夫John有两种移动方式：要么走路，要么传送。

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

* 传送: 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[];

 int main(){

     int n, k, now, nxt, i, j;

     scanf("%d%d", &n, &k);

     k <<= ;

     memset(data, 0x7F, sizeof data); data[n] = ;

     std::queue<int>q; q.push(n);

     while (!q.empty()){

         now = q.front(); q.pop();

         j = now ==  ?  : ;

         for (i = ; i < j; ++i){

             switch (i){

             case :nxt = now + ; break;

             case :nxt = now << ; break;

             case :nxt = now - ; break;

             }

             if (i< && nxt > k) continue;

             if (data[nxt] > data[now] + ){

                 data[nxt] = data[now] + ; q.push(nxt);

             }

         }

     }

     printf("%d\n", data[k >> ]);

     return ;

 }