hdu 2717 从n点走到k点 (BFS)

在横坐标上从n点走到k点至少要几步可以到 n+1 n-1 n*2这3个点
Sample Input
5 17
Sample Output
4
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 using namespace std;
 6 
 7 int n , k ;
 8 int ans ;
 9 bool v[100010] ;
10 
11 struct node
12 {
13     int x ;
14     int step ;
15 };
16 
17 bool yes(int x)
18 {
19     if (x>=0 && x<= 100010 && v[x] == 0)
20         return 1 ;
21     else
22         return 0 ;
23 }
24 
25 int bfs()
26 {
27     queue<node> q ;
28     node now , t ;
29     now.x = n ;
30     now.step = 0 ;
31     q.push(now) ;
32     memset(v , 0 , sizeof(v)) ;
33     v[n] = 1 ;
34     while(!q.empty())
35     {
36         now = q.front() ;
37         q.pop() ;
38         if (now.x == k)
39             return now.step ;
40         t.x = now.x + 1 ;
41         if (yes(t.x))
42         {
43             t.step = now.step + 1 ;
44             q.push(t) ;
45             v[t.x] = 1 ;
46         }
47         t.x = now.x - 1 ;
48         if (yes(t.x))
49         {
50             t.step = now.step + 1 ;
51             q.push(t) ;
52             v[t.x] = 1 ;
53         }
54         t.x = now.x * 2 ;
55         if (yes(t.x))
56         {
57             t.step = now.step + 1 ;
58             q.push(t) ;
59             v[t.x] = 1 ;
60         }
61 
62     }
63     return 0 ;
64 }
65 
66 int main ()
67 {
68 
69     while (scanf("%d %d" , &n , &k) != EOF)
70     {
71 
72         ans = bfs() ;
73         printf("%d
" , ans) ;
74     }
75 
76     return 0 ;
77 }
View Code