poj3278：catch the cow
这里贴上的都是原题，没有附上翻译的版本，大家英语都是杠杠的，想必都是无障碍阅读，实在读不懂，可以百度一下意思。
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?
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
Hint：
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
AC code 1：（这一段代码是参见网上比较优质的AC代码的）
#include<iostream> #include<cstdio> #include<queue> using namespace std; int n, k, c, ans; int num[100005]; //定义为全局变量，默认值都是0 int main() { while(cin>>n>>k) { ans = 0; queue<int> q; q.push(n); num[n] = 0; while(q.size()) { c = q.front(); if(c == k) { ans = num[c]; break; } q.pop(); if(!num[c-1] && c-1>=0) // !num[c-1]的意思是，如果c-1没有被执行过，那么就走一走，这就是代码为什么只能执行一次的原因，因为执行过了一次之后，num数组没有被再次置0，下一次循环到这里的时候，就进不去，那么结果就会出错， { //这种情况也可以另外设一个falg判断数组，像下面这样 !的意思是取反，0取反为>1的正数 num[c-1] = num[c] + 1; q.push(c-1); } if(c+1<=100000 && !num[c+1]) { num[c+1] = num[c] + 1; q.push(c+1); } if(c*2<=100000 && !num[2*c]) { num[2*c] = num[c] + 1; q.push(2*c); } } cout<<ans<<endl; } return 0; }
AC code 2：（这一段代码是在自己理解的基础上写的，个人觉得这一段代码理解起来比较容易，适合起步者）
#include<iostream> #include<cstdio> #include<queue> #include<cstring> //这个头文件是为了使用memset函数的 using namespace std; int num[100005]; bool flag[100005]; //这个是跟上面那个代码最大不同的地方，也是代码能够处理多组数据的原因； int main() { int n,k,c; while(cin>>n>>k) { int ans=0; memset(flag,false,sizeof(flag)); //每次开始给flag数组全部预置值为false queue<int> q; q.push(n); num[n]=0; while(q.size()) { c=q.front(); if(c==k) //如果已经找到了相对应的值，那么就记录下对应的num数组对应的值，然后循环跳出 { ans=num[c]; break; } q.pop(); //这又是容易错的地方，记得每次取出q的front之后，要把它pop出来 if(c-1>=0&&!flag[c-1]) //每进去一次都要给对应的flag数组的值置为true，表示已经走过了，防止重复走，死循环 { flag[c-1]=true; num[c-1]=num[c]+1; q.push(c-1); } if(c+1<=100000&&!flag[c+1]) { flag[c+1]=true; num[c+1]=num[c]+1; q.push(c+1); } if(c*2<=100000&&!flag[c*2]) { flag[c*2]=true; num[c*2]=num[c]+1; q.push(c*2); } } cout<<ans<<endl; } return 0; }
附上一张以5 17作为样例的图解，希望能帮到大家理解：
