poj 4001 抓住那头牛 （广度优先搜索算法）

总时间限制: 

2000ms 

内存限制: 

65536kB

描述

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

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

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

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

输入

两个整数，N和K

输出

一个整数，农夫抓到牛所要花费的最小分钟数

样例输入

5 17

样例输出

4

因为农夫每次移动的代价都是一样的，而广度优先搜索算法在权值一样时的解即为最佳解，所以此题用广度优先搜索算法就可以解决了。我们可以把农夫的所有状态看成一个三叉树，农夫的初始点为树的根节点，然后依次访问当前节点的三个孩子（+1，-1，*2），每访问一个节点时将该节点放入队列以实现广度优先搜索。最佳解出现时跳出循环，（因为此题必有解所以不同担心广度搜索不收敛的问题）。程序设置一个待访问坐标队列（实现广搜），一个坐标是否访问标志和一个距离数组（每个点到农夫起点的最短距离）具体实现看下面的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int queue[100001];
int distance[100001];
bool flag[100001];
int head,tail;

void en_queue(int x){
    queue[head++]=x;
}

int de_queue(){
    return queue[tail++];
}

bool empty(){
	if(head==tail)
		return true;
	return false;
}

int main(){
    int N,K,temp;
	while(scanf("%d%d",&N,&K)!=EOF){
		head=tail=0;
		memset(queue,0,sizeof(queue));
		memset(distance,0,sizeof(distance));
		memset(flag,0,sizeof(flag));
        en_queue(N);
		flag[N]=true;
		while(empty()==false){
			N=de_queue();
			if(N==K){
				printf("%d\n",distance[N]);
				break;
			} 
			temp=N+1;
			if(temp<=100000 && flag[temp]==false){
				flag[temp]=true;
				distance[temp]=distance[N]+1;
				en_queue(temp);
			}
			temp=N-1;
			if(temp>=0 && flag[temp]==false){
				flag[temp]=true;
				distance[temp]=distance[N]+1;
				en_queue(temp);
			}
			temp=N*2;
			if(temp<=100000 && flag[temp]==false){
				flag[temp]=true;
				distance[temp]=distance[N]+1;
				en_queue(temp);
			}
		}
	}
	return 0;
}