POJ 3278 Catch That Cow

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 35043 Accepted: 10800 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. USACO 2007 Open Silver

1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 const int maxn=100000;
 9 
10 int vis[maxn+10];
11 int n,k;
12 
13 struct node{
14     int x,c;
15 };
16 
17 int BFS(){
18     queue<node> q;
19     while(!q.empty())
20         q.pop();
21     memset(vis,0,sizeof(vis));
22     node cur,next;
23     cur.x=n,cur.c=0;
24     vis[cur.x]=1;
25     q.push(cur);
26     while(!q.empty()){
27         cur=q.front();
28         q.pop();
29         for(int i=0;i<3;i++){
30             if(i==0)
31                 next.x=cur.x-1;
32             else if(i==1)
33                 next.x=cur.x+1;
34             else
35                 next.x=cur.x*2;
36             next.c=cur.c+1;
37             if(next.x==k)
38                 return next.c;
39             if(next.x>=0 && next.x<=maxn && !vis[next.x]){
40                 vis[next.x]=1;
41                 q.push(next);
42             }
43         }
44     }
45     return 0;
46 }
47 
48 int main(){
49 
50     //freopen("input.txt","r",stdin);
51 
52     while(~scanf("%d%d",&n,&k)){
53         if(n>=k){
54             printf("%d\n",n-k);
55             continue;
56         }
57         printf("%d\n",BFS());
58     }
59     return 0;
60 }