追牛

给定出发坐标和牛的坐标，牛不动，然后去追牛

追的过程中有三种选择：当前坐标+1，当前坐标-1，当前坐标乘2，每种选择都花费一分钟时间

问追到牛的最短时间

例如

追逐方式的选择是5-10-9-18-17，花费四分种

思路：因为数据太大，用DFS肯定会超时，但是可以发现，对于某一个点，无论是+1还是-1还是*2，这些操作能到达的点都是不同的且到这些点的距离都是对它而言最短的

所以可以用BFS，只是更新状态的方式和走方格式的BFS不太一样，但是核心思想不变

#include<iostream>
#include<stdio.h>
#include<queue>

using namespace std;

const int INF = 1000000;
int n, k;
int d[1000000];

void bfs(int start){
  for(int i=0; i<=100000; i++)
    d[i] = INF;
  queue<int> q;
  q.push(start);
  d[start] = 0;
  int a = INF;
  while(!q.empty()){
    int t = q.front(); q.pop();
    for(int i=0; i<3; i++){
      int next;
      switch(i){
          case 0: next = t+1;break;
          case 1: next = t-1;break;
          case 2: next = t*2;break;
          default: break;
        }
      if(next >= 0 && next <= 100000 && d[next] == INF){
        q.push(next);
        d[next] = d[t]+1;
      }
    }

  }
}

int main(){
  ios::sync_with_stdio(false);
  while(~scanf("%d%d", &n, &k)){
    bfs(n);
    cout << d[k] << endl;
  }
  return 0;
}