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
[hit : (5->17) 5-10-9-18-17 , 一共走了4步 。]
理解
John的牛跑了，他要用最快的方式抓到这头牛，他可以选择后退一步或者前进一步甚至前进当前所在坐标的二倍，找出最快的路径帮他抓到牛。
代码部分
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int con,x,y,f,b[200000];//数组开到这里是极限，再小就会数据溢出。
queue<int>a;
int main()
{
while(scanf("%d%d",&x,&y)!=EOF)
{
while(!a.empty())
{
a.pop();
}
memset(b,0,sizeof(b));
a.push(-2);
con=0;
f=0;
if(x==y)
{printf("0\n");continue;}
a.push(x);
b[x]=1;
int i=1;
while(f!=1)
{
if(a.front()==-2)
{
a.pop();
con++;
a.push(-2);
}
if((a.front()-1)==y||(a.front()+1)==y||(a.front()*2)==y)
{f=1;break;}
if(b[a.front()-1]==0&&a.front()>1&&a.front()<100001)
{a.push(a.front()-1);b[a.front()-1]=1;}//b数组是存在标记，表示出现过这个数了下次就不要再次运算，可以提高程序效率。
if(b[a.front()+1]==0&&a.front()>-1&&a.front()<99999)
{a.push(a.front()+1);b[a.front()+1]=1;}
if(b[a.front()*2]==0&&a.front()>0&&a.front()<50001)
{a.push(a.front()*2);b[a.front()*2]=1;}
a.pop();
//cout<<i++<<endl;
}
printf("%d\n",con);
}
return 0;
}
