poj3278Catch That Cow（bfs）

每次有三种决策：加一||减一||乘二。
 1 #include<cstring>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 
 6 const int maxn=200010;
 7 int vis[maxn];
 8 int n,k;
 9 
10 struct node
11 {
12     int x,d;
13 }now,nex;
14 
15 int bfs(int n)
16 {
17     queue<node> q;
18     now.x=n;
19     now.d=0;
20     q.push(now);
21     vis[n]=1;
22     while(!q.empty())
23     {
24         now=q.front();
25         q.pop();
26         if(now.x==k) return now.d;
27         for(int i=0;i<3;i++)
28         {
29             if(i==1)  nex.x=now.x+1;
30             else if(i==0) nex.x=now.x-1;
31             else nex.x=now.x*2;
32             if(nex.x>=0&&nex.x<maxn&&!vis[nex.x]) //注意边界情况！
33             {   
34                 vis[nex.x]=1;
35                 nex.d=now.d+1;
36                 q.push(nex);
37             }
38         }
39     }
40     return -1;
41 }
42 int main()
43 {
44     while(scanf("%d%d",&n,&k)!=EOF)
45     {
46         memset(vis,0,sizeof(vis));
47         if(k<=n) printf("%d
",n-k);
48         else  printf("%d
",bfs(n));
49     }
50     return 0;
51 
52 }