1253：抓住那头牛

时间限制: 1000 ms

内存限制: 65536 KB

提交数: 28039

通过数: 11162

【题目描述】 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000) ，牛位于点K(0≤K≤100000) 。农夫有两种移动方式：

1、从X 移动到X−1 或X+1 ，每次移动花费一分钟

2、从X移动到2×X ，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

【输入】 两个整数，N 和K 。

【输出】 一个整数，农夫抓到牛所要花费的最小分钟数。

【输入样例】 5 17 【输出样例】 4

```cpp
#include<bits/stdc++.h> 
using namespace std;
struct node{
	int x;
	int time;
};
node q[100000];
int qx,zx;
int v[100000];
int h,t;
int dx[3]={1,-1,0};
void bfs(){
	q[t].x=qx;
	q[t].time=0;
	v[qx]=1;
	t++;
	while(h<t){
		for(int i=0;i<3;i++){
			int xx=q[h].x+dx[i];
			if(i==2){
				xx+=xx;
			}
			if(xx>=qx&&v[xx]==0){
				v[xx]=1;
				q[t].x=xx;
				q[t].time=q[h].time+1;
				if(xx==zx){
					cout<<q[t].time;
					return ;
				}
				t++;
			}
		}
		h++;
	}
}
int main(){
	cin>>qx>>zx;
	bfs();
	return 0;
}