Catch That Cow
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 146523 Accepted: 45039
Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  • Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
  • Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K
Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input

5 17
Sample Output

4
Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

bfs就行了，把它想象成一颗3叉树，然后每次，每个节点有3个根节点，根节点的规则是当前节点-1，+1，*2，然后扩展这棵树，当某个节点等于k，更新步数，用这个数组step存储step[i]:表示从n到i节点需要的步数，选个最小值就行了，每次扩展树的时候剪一下枝。
代码：

#include<iostream>
#include<queue>
using namespace std;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int minn=inf,n,k;
int vis[maxn],step[maxn];

void bfs(int n){
	int next;
	queue<int>st;
	st.push(n);
	vis[n]=1;
	step[n]=0;
	while(!st.empty()){
		int now=st.front();st.pop();
		for(int i=1;i<=3;i++){
			if(i==1)next=now-1;
			if(i==2)next=now+1;
			if(i==3)next=now*2;
			if(next<0||next>k+1)continue;//剪枝 next>k+1，next可以为k+1，但是不能为k+2，因为k+1回退一布就已经是最短距离了
			if(!vis[next]){
				st.push(next);
				step[next]=step[now]+1;
				vis[next]=1;
			}
			if(next==k){
				minn=min(minn,step[next]);
			}
		}
	} 
}
int main(){
	scanf("%d%d",&n,&k);
	if(n>=k){
		cout<<n-k<<endl;
	}else{
		bfs(n);
		cout<<minn<<endl;
    }
}