Catch That Cow
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 37107 | Accepted: 11470 |
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
1 #include<stdio.h> 2 #include<queue> 3 #include<string.h> 4 using namespace std; 5 int vis[100005]; 6 int N,K,time; 7 struct node 8 { 9 int x; 10 int step; 11 }info; 12 void bfs(int n) 13 { 14 int i; 15 info.x=n; 16 info.step=0; 17 vis[n]=1; 18 queue<node>q; 19 q.push(info); 20 while(!q.empty()) 21 { 22 node pos; 23 pos=q.front(); 24 q.pop(); 25 if(pos.x==K) 26 { 27 time=pos.step; 28 return ; 29 } 30 for(i=0;i<3;i++) 31 { 32 int xx,step; 33 if(i==0) 34 { 35 xx=pos.x+1; 36 step=pos.step+1; 37 } 38 else if(i==1) 39 { 40 xx=pos.x-1; 41 step=pos.step+1; 42 43 } 44 else 45 { 46 xx=2*pos.x; 47 step=pos.step+1; 48 } 49 if(xx>=0&&xx<=100000&&!vis[xx]) 50 { 51 vis[xx]=1; 52 info.x=xx; 53 info.step=step; 54 q.push(info); 55 } 56 } 57 } 58 } 59 int main() 60 { 61 while(scanf("%d %d",&N,&K)!=EOF) 62 { 63 memset(vis,0,sizeof(vis)); 64 bfs(N); 65 printf("%d ",time); 66 } 67 return 0; 68 }