2014
02-14

# 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?

Line 1: Two space-separated integers: N and K

Line 1: Two space-separated integers: N and K

5 17

4

HintThe 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. 

BFS 三个方向即可；

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<fstream>
#include<queue>
#define MAX 100010
using namespace std;
int n,k;
int  cur,next;
int step[MAX];
queue<int>q;
void bfs()
{
while(!q.empty())
{
cur=q.front();
q.pop();
if(cur==k)  break;
next=cur-1;
if(next>=0&&step[next]==0)
{
q.push(next);
step[next]=step[cur]+1;
}
next=cur+1;
if(step[next]==0)
{
q.push(next);
step[next]=step[cur]+1;
}
next=cur*2;
if(next<=100000&&(next-k)<(k-cur)&&step[next]==0)
{
q.push(next);
step[next]=step[cur]+1;
}
}

}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(step,0,sizeof(step));
if(n>k)
cout<<(n-k)<<endl;
else
{
while(!q.empty()) q.pop();
q.push(n);
bfs();
cout<<step[k]<<endl;
}
}
return 0;
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯

2. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

3. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。