题目链接：http://poj.org/problem?id=3278

 

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

题目大意：在一个（0 ≤ l≤ 100,000）的数轴上，有一个人在n处，一头牛在k处，人要抓牛，牛不动；

人可以向前走一步，或者向后走一步，或者跳到当前位置的2倍的距离；这三种移动方式，问最少几步抓到牛：

很显然，如果人在牛前面，人只能向后走，那么只能是n-k步，但如果牛在前面，就有很多种方法了，很显然，宽搜很好。。

宽搜与深搜不同，宽搜运用队列，不需要递归，只用循环知道队列中元素个数为空时就结束，而深搜则是递归知道符合终止条件才结束，两者运用对象不同：

ac代码：

 

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

#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long
#define da    10000000
#define xiao -10000000
#define clean(a,b) memset(a,b,sizeof(a))

int shuzu[100010];
bool biaoji[100010];
int n,k;

queue<int> s;

void bfs(int a,int b)
{
	int i,j;
	s.push(a);
	shuzu[a]=0;
	biaoji[a]=1;
	while(s.size())					//队列为空时说明所有的都搜索完了 
	{
		int x=s.front();
		s.pop();
		for(i=0;i<3;++i)			//三种情况 
		{
			int can;
			if(i==0)				//后退一步 
				can=x-1;
			else if(i==1)			//前进 
				can=x+1;
			else					//跳 
				can=x*2;
			if(can>100000||can>4*k||can<0)		//超出太多了就结束此次，相当于这个路径弃掉 
				continue;
			if(biaoji[can]==0)					//第一次出现的必定是最短的 
			{
				shuzu[can]=shuzu[x]+1;			//路径 记录步数 
				biaoji[can]=1;					//路径标记 
				s.push(can);					//将这个路径计入队列 
			}
			if(can==k)							//如果找到就结束循环 
				return ； 
		}
	}
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
    	clean(shuzu,0);
    	clean(biaoji,0);
    	while(s.size())
    		s.pop();
    	if(n>=k)
    	{
    		printf("%d\n",n-k);					//只能往后走 
    		continue;
		}
		bfs(n,k);
		printf("%d\n",shuzu[k]);				//输出最短步数 
	}
}

 

 

 

 

 

 

bfs