POJ 3278 Catch That Cow

Catch That Cow

Time Limit: 2000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 3278
64-bit integer IO format: %lld Java class name: Main

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

Source

USACO 2007 Open Silver

解题：搜。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 struct node{
18     int p,step;
19     node(int x = 0,int y = 0):p(x),step(y){}
20 };
21 int n,k;
22 bool vis[100100];
23 queue<node>q;
24 int bfs(){
25     while(!q.empty()) q.pop();
26     memset(vis,false,sizeof(vis));
27     vis[n] = true;
28     q.push(node(n,0));
29     int tmp;
30     while(!q.empty()){
31         node now = q.front();
32         q.pop();
33         if(now.p == k) return now.step;
34         tmp = now.p+1;
35         if(tmp <= 100000 && !vis[tmp]){
36             vis[tmp] = true;
37             q.push(node(tmp,now.step+1));
38         }
39         tmp = now.p-1;
40         if(tmp >= 0 && !vis[tmp]){
41             vis[tmp] = true;
42             q.push(node(tmp,now.step+1));
43         }
44         tmp = now.p<<1;
45         if(tmp <= 100000 && !vis[tmp]){
46             vis[tmp] = true;
47             q.push(node(tmp,now.step+1));
48         }
49     }
50     return -1;
51 }
52 int main() {
53     while(~scanf("%d %d",&n,&k))
54         printf("%d
",bfs());
55     return 0;
56 }

View Code