poj 3278 bfs

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 100001;
 7 bool visit[N];
 8 
 9 struct Node
10 {
11     int x, step;
12 
13     Node () {}
14 
15     Node ( int _x, int _step )
16     {
17         x = _x, step = _step;
18     }
19 
20 } q[N];
21 
22 bool ok( int x )
23 {
24     return x >= 0 && x < N && !visit[x];
25 }
26 
27 int bfs( int src, int des )
28 {
29     memset( visit, 0, sizeof(visit) );
30     int head = 0, tail = 0;
31     q[tail++] = Node( src, 0 );
32     visit[src] = 1;
33     while ( head < tail )
34     {
35         Node t = q[head++];
36         if ( t.x == des ) return t.step;
37         if ( ok( t.x + 1 ) )
38         {
39             q[tail++] = Node( t.x + 1, t.step + 1 );
40             visit[t.x + 1] = 1;
41         }
42         if ( ok( t.x - 1 ) )
43         {
44             q[tail++] = Node( t.x - 1, t.step + 1 );
45             visit[t.x - 1] = 1;
46         }
47         if ( ok( t.x * 2 ) )
48         {
49             q[tail++] = Node( t.x * 2, t.step + 1 );
50             visit[t.x * 2] = 1;
51         }
52     }
53     return -1;
54 }
55 
56 int main()
57 {
58     int s, t;
59     while ( scanf("%d%d", &s, &t) != EOF )
60     {
61         printf("%d\n", bfs( s, t ));
62     }
63     return 0;
64 }