POJ 3278 Catch That Cow

注：本人英语很渣，题目大意大多来自百度~=0=

题目大意

农民约翰需要抓住他的牛，他和他的牛在一条直线上（估计是一维生物），约翰在N (0 ≤ N ≤ 100,000)处，他的牛在 K (0 ≤ K ≤ 100,000) ，约翰下次可以从x移动到x+1或者x-1或者2*x的地方，问约翰最少需要多少步才能找到他的牛。

用BFS可以解决~ 不过需要剪枝不然会MLE

值得一提的一点是步数不要用结构体保存或许是我剪枝不够好用结构体保存会MLE

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <cctype>
 8 #define N 200010
 9 using namespace std;
10  
11 bool maps[N];//用来判断此点约翰有没有走过
12 int a, b, step[N];//a, b 为分别为N, K， //step[i]用来保存约翰走到i点时用了几步 （注 ： 不要用结构体保存步数， 不然有可能MLE）
13  
14 void BFS()
15 {
16     int q1 = a;
17     maps[a] = true;
18     queue<int>q;
19     q.push(q1);
20  
21     while(!q.empty()) {
22         int q2 = q.front();
23         q.pop();
24         if(q2 == b) {//找到之后输出走了几步
25             printf("%d
", step[q2]);
26             return ;
27         }
28         //约翰向走 -1 只有此时他的坐标为正数才会走
29         int x = q2 - 1;
30         if(!maps[x] && q2 > 0) {
31             maps[x] = true;
32             q1 = x;
33             step[q1] = step[q2] + 1;
34             q.push(q1);
35         }
36         //由于约翰向后走只能 -1  所以只在q2 < b时才向前走
37         if(q2 < b){
38         x = q2 + 1;
39         if(!maps[x]) {
40             maps[x] = true;
41             q1 = x;
42             step[q1] = step[q2] + 1;
43             q.push(q1);
44         }
45         x = q2 * 2;
46         if(!maps[x]) {
47             maps[x] = true;
48             q1 = x;
49             step[q1] = step[q2] + 1;
50             q.push(q1);
51         }
52         }
53  
54     }
55 }
56  
57 int main()
58 {
59     while(~scanf("%d %d", &a, &b)){
60         memset(maps, 0, sizeof(maps));
61         BFS();
62     }
63     return 0;
64 }