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的牛跑了，他要用最快的方式抓到這頭牛，他可以選擇后退一步或者前進(jìn)一步甚至前進(jìn)當(dāng)前所在坐標(biāo)的二倍，找出最快的路徑幫他抓到牛。
代碼部分
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int con,x,y,f,b[200000];//數(shù)組開到這里是極限，再小就會(huì)數(shù)據(jù)溢出。
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數(shù)組是存在標(biāo)記，表示出現(xiàn)過這個(gè)數(shù)了下次就不要再次運(yùn)算，可以提高程序效率。
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;
}
