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
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.
求n到k需要多少步变化有（n+1,n-1，n*2）三种选择；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
#define N 100010 int m,n;
int vis[N];
struct node
{
int x,step;
friend bool operator<(node a,node b)
{
return a.step>b.step;
}
}; int dfs()
{
priority_queue<node>Q;
memset(vis,,sizeof(vis));
node q,s;
s.x=n;
vis[s.x]=;
s.step=;
Q.push(s);
int i;
while(!Q.empty())
{
q=Q.top();
Q.pop();
if(q.x==m)
return q.step;
for(i=;i<;i++)
{
if(i==)
s.x=q.x+;
else if(i==)
s.x=q.x-;
else if(i==)
s.x=q.x*;
if(s.x<&&s.x>=&&vis[s.x]==)//vis[s.x]==0必须放到后面，-_-被运行错误错了好多次；
{
vis[s.x]=;
s.step=q.step+;
Q.push(s);
} }
}
return -;//要有返回值，我也不知道为什么；
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==n)
{
printf("0\n");
continue;
}
int ans;
ans=dfs();
printf("%d\n",ans);
}
return ;
}