Catch That Cow

原题

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  #include  #include  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; }