poj3278（抓住那头牛）

题意：农夫在x点牛在y点，农夫前进或者后退花费一分钟，前进两倍花费2分钟，求花费最少的时间抓住牛

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 100010 ;
int stamp[N] ;
bool vis[N] ;
int dir[3] ;
queue<int> q ;
void bfs(int n , int k){
     int head ;
     q.push(n);
     vis[n] = true ;
     stamp[n] = 0 ;
     while(!q.empty()){
         head = q.front();
         q.pop();
         if (head == k){   //抓住牛了，可跳出循环   
              cout << stamp[k] << endl ;      
              break ;
         }
         dir[0] = head - 1 ;
         dir[1] = head + 1 ;
         dir[2] = head * 2 ;
         for (int i = 0 ; i < 3 ; i ++){
              if (dir[i] >= 0 && dir[i] < N && vis[dir[i]]==false){ //不能dir[i]>0否则会WA
                  vis[dir[i]] = true ;
                  stamp[dir[i]] = stamp[head] + 1 ;
                  q.push(dir[i]);
                  if (dir[i] > k)   //人在牛的前面就不用再前进了（剪枝）
                       break ;
              }
         }
     }
}
int main(){
     int n , k ;
     cin >> n >> k ;
     bfs(n,k);
     return 0 ;
}