原题
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.
策略
策略1 深度优先搜索
从起点出发，随机挑一个方向，能往前走就往前走（扩展），走不动了则回溯。
不能走已经走过的点（要判重）。
要想求最优解，则要遍历所有走法。可以用各种手段优化，比如，若已经找到路径长度为n的解，则所有大于n的走法就不必尝试。
运算过程中需要存储路径上的节点，数量较少。用栈存节点。
策略2 广度优先搜索
给节点分层。起点是第0层。从起点最少需要n步就能到达的点属于第n层。
依层次顺序，从小到大扩展节点。把层次低的点全部扩展出来后，才会扩展层次高的点。
扩展时不能扩展已经走过的节点（要判重）。
可确保找到最优解，但是因扩展出来的节点较多，且多数节点都需要保存，因此需要的存储空间较大。用队列存储节点。
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int N,K;
const int MAXN=100000;
int visited[MAXN+10]; //判重标记，visited[i]=true表示i已经扩展过
struct step
{
int x; //位置
int steps; //到达x所需的步数
step(int xx,int s):x(xx),steps(s){}
};
queue<step> q; //队列，即open表
int main()
{
cin>>N>>K;
memset(visited,0,sizeof(visited));
q.push(step(N,0));
visited[N]=1;
while(!q.empty())
{
step s=q.front();
if(s.x==K)
{//找到目标
cout<<s.steps<<endl;
return 0;
}
else
{
if(s.x-1>=0&&!visited[s.x-1])
{
q.push(step(s.x-1,s.steps+1));
visited[s.x-1]=1;
}
if(s.x+1<=MAXN&&!visited[s.x+1])
{
q.push(step(s.x+1,s.steps+1));
visited[s.x+1]=1;
}
if(s.x*2<=MAXN&&!visited[s.x*2])
{
q.push(step(s.x*2,s.steps+1));
visited[s.x*2]=1;
}
q.pop();
}
}
return 0;
}