题目链接：https://vjudge.net/problem/POJ-3278
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.
分析：
Farmer John要在一条数轴上用最快的速度走到一个定点
他每次都有三种走法：
①前移一格
②后移一格
③前移x格（x为当前的位置）
可以抽象为向三个方向搜索的广搜
（因为是最优解问题所以用广搜）
时间复杂度分析：
在不剪枝的情况下， 每次有三个方向
那么走一步有3种可能；
走两步就是3*3种可能；
走三步就是3*3*3种可能；
那么也就是3^n次搜索（n为找到答案所需的最少步数）
而这道题考虑较坏的情况，从1走到100000；
最快的走法是每次×2，那么也需要将近17次吧（2^17=131072)
如果不剪枝，搜索次数将达到恐怖的3^17，肯定tle；
如何剪枝：
①首先想到如果farmer 在数轴上靠后的位置，而cow在数轴上靠前的位置
比如farmer在100，cow在2；
那么显然因为farmer只有一种走法能往回走（也就是x-1），这种情况可以直接算出答案（否则你得走98步，时间复杂度必然爆炸）
②其次，想到了用vis数组记忆走过的点
因为广搜是一层层往外搜的，如果你当前搜到的点是已经被搜过了，那么你这条路必然不是最快的路。
AC代码：
#include <cstdio> #include <queue> #include <string.h> #include <iostream> using namespace std; int N,K; int vis[100005]; typedef struct{ int pos; int step; }node; node bfs(int N){ queue<node>q; node start; start.pos=N; start.step=0; vis[N]=1; q.push(start); while(!q.empty()){ node temp=q.front(); q.pop(); if(temp.pos==K) return temp; for(int i=1;i<=3;i++){ node t; t.step=temp.step+1; if(i==1) t.pos=2*temp.pos; else if(i==2) t.pos=temp.pos-1; else t.pos=temp.pos+1; if(t.pos>=0&&t.pos<=100000&&!vis[t.pos]){ vis[t.pos]=1; q.push(t); } } } } int main() { memset(vis,0,sizeof(vis)); scanf("%d%d",&N,&K); if(N>K){ printf("%d",N-K); } else{ node ret=bfs(N); printf("%d",ret.step); } return 0; }
