poj3278（Catch That Cow）

题目大意：
一位农夫追赶一头牛，题目给出农夫和牛的坐标分别为N,K。农夫可以通过坐标的加一或减一也可以坐标乘以2。问你最少多少步到达牛的坐标。
解题思路;
简单BFS。
代码:
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <sstream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <string>
 8 #include <bitset>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 #include <list>
14 //#include <map>
15 #include <set>
16 using namespace std;
17 /***************************************/
18 #define ll long long
19 #define int64 __int64
20 #define PI 3.1415927
21 /***************************************/
22 const int INF = 0x7f7f7f7f;
23 const double eps = 1e-8;
24 const double PIE=acos(-1.0);
25 const int d1x[]= {0,-1,0,1};
26 const int d1y[]= {-1,0,1,0};
27 const int d2x[]= {0,-1,0,1};
28 const int d2y[]= {1,0,-1,0};
29 const int fx[]= {-1,-1,-1,0,0,1,1,1};
30 const int fy[]= {-1,0,1,-1,1,-1,0,1};
31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1};
32 const int diry[]= {-2,-2,-1,-1,1,1,2,2};
33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/
34 /***************************************/
35 void openfile()
36 {
37     freopen("data.in","rb",stdin);
38     freopen("data.out","wb",stdout);
39 }
40 priority_queue<int> qi1;
41 priority_queue<int, vector<int>, greater<int> >qi2;
42 /**********************华丽丽的分割线,以上为模板部分*****************/
43 int vis[200009],cnt[200009];
44 int BFS(int n,int k)
45 {
46     queue<int >Q;
47     Q.push(n);
48     int v;
49     while(!Q.empty())
50     {
51         v=Q.front();
52         Q.pop();
53         if (v==k)
54             return cnt[k];
55         if (v<100005&&v>-2)
56         {
57             if (!vis[v-1])
58             {
59                 Q.push(v-1);
60                 if (!cnt[v-1])
61                     cnt[v-1]=cnt[v]+1;
62                 vis[v-1]=1;
63             }
64             if (!vis[v+1])
65             {
66                 Q.push(v+1);
67                 if (!cnt[v+1])
68                     cnt[v+1]=cnt[v]+1;
69                 vis[v+1]=1;
70             }
71             if (!vis[v*2])
72             {
73                 Q.push(v*2);
74                 if (!cnt[v*2])
75                     cnt[v*2]=cnt[v]+1;
76                 vis[v*2]=1;
77             }
78         }
79     }
80     return 0;
81 }
82 int main()
83 {
84 
85     int n,k,sum;
86     while(scanf("%d%d",&n,&k)!=EOF)
87     {
88         memset(vis,0,sizeof(vis));
89         memset(cnt,0,sizeof(cnt));
90         sum=BFS(n,k);
91         printf("%d
",sum);
92     }
93     return 0;
94 }
View Code