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.
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 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\n",bfs());
55 return 0;
56 } View Code
夜空中最亮的星，照亮我前行