Catch That Cow

5 17

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.
 

刚开始用的DFS，没看清数据量，超时是必须的。 后改成BFS进行搜索。能搜到的所有坐标只能是0-k+1.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <climits>

using namespace std;

const int MAX = 100002;


int n,k,ans;
int dist[MAX];
queue<int> que;

bool yes(int x){
	if(x>=0 && x<=k+2 && dist[x]==-1)return true;
	return false;
}

int bfs(int x){
	que.push(x);
	dist[x] = 0;

	while(!que.empty()){
		x = que.front();
		que.pop();
		if(x==k)break;
		if(yes(x+1)){
			dist[x+1] = dist[x] + 1;
			que.push(x+1);
		}
		if(yes(x-1)){
			dist[x-1] = dist[x] + 1;
			que.push(x-1);
		}
		if(yes(x*2)){
			dist[2*x] = dist[x] + 1;
			que.push(2*x);
		}
	}
	return dist[k];
}

int main(){
	//freopen("in.txt","r",stdin);

	while(scanf("%d %d",&n,&k)!=EOF){
		if(n>=k){
			printf("%d\n",n-k);
			continue;
		}
		while(!que.empty()){
			que.pop();
		}
		ans = INT_MAX;
		memset(dist,-1,sizeof(dist));
		ans = bfs(n);
		printf("%d\n",ans);
	}
    return 0;
}

HDU 2717 Catch That Cow,布布扣,bubuko.com

HDU 2717 Catch That Cow

原文：http://blog.csdn.net/iaccepted/article/details/23787271