poj-3278

poj 3278

1. 如果FJ不在奶牛后面,只有一种移动方式，直接输出N-k就可以
2. 否则使用bfs搜索答案即可，在搜索时有三种移动方式

   #include <iostream>
   #include <queue>
   #include <algorithm>
   #include <cstring>
   
   using namespace std;
   
   #define maxn 100005
   
   queue<int> que;
   bool vis[maxn];
   int step[maxn];
   int n, k;
   
   void clear(queue<int>& q) {
       queue<int> empty;
       swap(empty, q);
   }
   
   int bfs() {
       que.push(n);
       int t = -1, next = -1;
       while(!que.empty()) {
           t = que.front();
           que.pop();
           for(int i = 0;i < 3;i++) {
               if(i == 0)  next = t - 1;
               else if(i == 1) next = t + 1;
               else next = t * 2;
   
               if(next < 0 || next > 100000) continue;
               if(!vis[next]) {
                   que.push(next);
                   step[next] = step[t] + 1;
                   vis[next] = true;
               }
               if(next == k) return step[next];
           }
       }
   
   }
   int main()
   {
       while(cin >> n >> k) {
           //cin >> n >> k;
           if(n >= k) {cout << (n - k) << endl; continue;}
           //初始化
           memset(vis, false, sizeof(vis));
           memset(step, 0, sizeof(step));
           clear(que);
   
           int ans = bfs();
           cout << ans << endl;
       }
       return 0;
   }