「BZOJ1646」[Usaco2007 Open] Catch That 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
Farmer John starts at point 5 and the fugitive cow is at point 17.
Sample Output
OUTPUT DETAILS:
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.
题解
裸的bfs。。。最大值设为max（n,k）+1，就可以了，证明略。。
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #define N 100001 using namespace std; int n,k,T,q[N],d[N]; bool inq[N]; void bfs() { memset(d,127,sizeof(d)); int t=0,w=1; q[0]=n;inq[n]=1;d[n]=0; while(t<w) { int now=q[t];t++;if(t==N)t=0; if(now<T&&d[now+1]>d[now]+1) { d[now+1]=d[now]+1; if((now+1)==n)return; if(!inq[now+1]) {inq[now+1]=1;q[w++]=now+1;if(w==N)w=0;} } if(now>0&&d[now-1]>d[now]+1) { d[now-1]=d[now]+1; if((now-1)==n)return; if(!inq[now-1]) {inq[now-1]=1;q[w++]=now-1;if(w==N)w=0;} } if((now<<1)<=T&&d[now<<1]>d[now]+1) { d[now<<1]=d[now]+1; if((now<<1)==n)return; if(!inq[now<<1]) {inq[now<<1]=1;q[w++]=(now<<1);if(w==N)w=0;} } } } int main() { scanf("%d%d",&n,&k); T=max(n,k)+1; bfs(); printf("%d",d[k]); return 0; } |
OI 课件=>
