本文主要是介绍POJnbsp;nbsp;3278nbsp;nbsp;Catchnbsp;Thatnbsp;Cow，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Catch That Cow
| Time Limit: 2000MS | | Memory Limit: 65536K |
| Total Submissions: 24664 | | Accepted: 7604 |
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.
Source
USACO 2007 Open Silver
泪奔了，跑了797MS，简单BFS，注意n==k的情况，还有如果n>=k，直接就可以判断是n-k了
代码（附测试数据）：
#include<stdio.h>
typedef struct point{
int x,step;
}target;
target que[5000000];
int map[5000000]={0},k;
int BFS(int n)
{
int i,end,top;
target next,in;
if(n==k)
return 0;
end=top=0;
que[top].x=n;
que[top].step=0;
while(top>=end)
{
in=que[end];
end=(end+1)% 5000000;
for(i=0;i<3;i++)
{
if(i==0)
next.x=in.x+1;
else if(i==2)
next.x=in.x-1;
else next.x=in.x*2;
if(next.x==k)
return in.step+1;
if(next.x>=0&&next.x<5000000&&map[next.x]==0)
{
map[next.x]=1;
top=(top+1)% 5000000;
next.step=in.step+1;
que[top]=next;
}
}
}
return 0;
}
int main()
{
int num,n;
scanf("%d%d",&n,&k);
map[n]=1;
if(k<=n)
num=n-k;
else
num=BFS(n);
printf("%d\n",num);
return 0;
}
测试数据：
1 1
0
1 5
3
5 1
4
1 100000
21
200 100000
16
13 15000
15
21 4500
14
64 7913
12
15 438
8
159 753
32
486 4267
52
147 963
31
486 15347
14
这篇关于POJnbsp;nbsp;3278nbsp;nbsp;Catchnbsp;Thatnbsp;Cow的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
