題目鏈接：http://poj.org/problem?id=3278 我會說這是我人生中第一道廣搜題么？？
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define maxn 100010
9 #define maxl 500010
10 int dir[3][2] = {{1, 1}, {1, -1}, {2, 0}};
11 int timet[maxn], S, T, q[maxl];
12 int n, k;
13 void init()
14 {
15 for (int i = 0; i < maxn; i++) timet[i] = -1;
16 S = n; T = k;
17 }
18 bool IN(int x)
19 {
20 return x >= 0 && x <= maxn;
21 }
22 void bfs()
23 {
24 int h = 0, t = 0;
25 timet[S] = 0;
26 q[t] = S;
27 t++;
28 while (h != t)
29 {
30 int x = q[h];
31 h = h % maxl + 1;
32 for (int i = 0; i < 3; i++)
33 {
34 int xx = x * dir[i][0] + dir[i][1];
35 if (!IN(xx)) continue;
36 if (timet[xx] == -1 || timet[x] + 1 < timet[xx])
37 {
38 timet[xx] = timet[x] + 1;
39 q[t] = xx;
40 t = t % maxl + 1;
41 }
42 }
43 }
44 }
45 int main()
46 {
47 while (~scanf("%d%d", &n, &k))
48 {
49 init();
50 bfs();
51 printf("%d\n", timet[T]);
52 }
53 return 0;
54 }
55
|