Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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.
//借鉴网上的，代码很强大，也很简洁。思路就是利用广搜直接判断出到达某一位置最短步数
#include<cstdio> #define N 100005 int u,v,x,f[N],q[N*2],h,t; int main() { scanf("%d%d",&u,&v); q[t++]=u; while(h<t) { u=q[h++]; if(u==v) { printf("%d\n",f[u]); break; } x=f[u]+1; if(u>0&&!f[u-1]) f[q[t++]=u-1]=x; if(u<=N&&!f[u+1]) f[q[t++]=u+1]=x; if(u*2<=N&&!f[u*2]) f[q[t++]=u*2]=x; } }