Problem 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?
* 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
思路：
当n>=k的时候只能后退一步
所以就是n-k
n<k的时候有三种 +1 -1 *2
BFS
参考代码
1 #include <stdio.h> 2 #include <string.h> 3 int bfs(int n,int k); 4 #define LEN 100001 5 int step[LEN]={0}; 6 int mark[LEN]={0}; 7 int main() 8 { 9 int n,k; 10 while(scanf("%d%d",&n,&k)!=EOF) 11 { 12 if(n>=k) 13 printf("%d\n",n-k); 14 else 15 printf("%d\n",bfs(n,k)); 16 } 17 return 0; 18 } 19 20 int bfs(int n,int k) 21 { 22 memset(step,0,sizeof(step)); 23 memset(mark,0,sizeof(mark)); 24 int queue[LEN]; 25 int i,front=0,rear=1; 26 queue[0]=n; 27 mark[queue[0]]=1; 28 while(front<rear) 29 { 30 for(i=0;i<3;i++) 31 { 32 if(queue[front]-1>=0&&!mark[queue[front]-1]) 33 { 34 mark[queue[front]-1]=1; 35 step[queue[front]-1]=step[queue[front]]+1; 36 queue[rear++]=queue[front]-1; 37 if(queue[rear-1]==k) 38 return step[queue[front]-1]; 39 } 40 if(queue[front]+1<=LEN&&!mark[queue[front]+1]) 41 { 42 mark[queue[front]+1]=1; 43 step[queue[front]+1]=step[queue[front]]+1; 44 queue[rear++]=queue[front]+1; 45 if(queue[rear-1]==k) 46 return step[queue[front]+1]; 47 } 48 if(queue[front]*2<=LEN&&!mark[queue[front]*2]) 49 { 50 mark[queue[front]*2]=1; 51 step[queue[front]*2]=step[queue[front]]+1; 52 queue[rear++]=2*queue[front]; 53 if(queue[rear-1]==k) 54 return step[queue[front]*2]; 55 } 56 } 57 front++; 58 } 59 }