题目链接：http://poj.org/problem?id=3278
这几次都是每天的第一道题都挺顺利，然后第二道题一卡一天。 = =，今天的这道题7点40就出来了，不知道第二道题在下午7点能不能出来。0 0
先说说这道题目，大意是有个农夫要抓牛，已知牛的坐标，和农夫位置。
并且农夫有三种移动方式，X + 1，X - 1，X * 2。问最少几步抓到牛。
開始觉得非常easy的，三方向的BFS就能顺利解决。然后在忘开标记的情况下直接广搜，果然TLE，在你计算出最少位置之前。牛早跑了。
然后反应过来开标记。来节约时间，然后发现竟然RE了，预计是标记数组不够大，毕竟有一个方向的x * 2。
然后打算控制一下查找范围。由于当X到达某个范围之后，在变为K，肯定不会是最少路径。
比方。当X已经大于K了。再运行X + 1， X * 2,肯定不会最短的得到K，然后在推断标记的时候做了优化。
然后就过掉了。
我再去百度。看看有没有更好的方法，发现我这种方法就叫剪枝啊 = =。吓尿、
代码例如以下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h> #define LEN 1000000
struct node
{
int num,t;
}q[LEN]; bool vis[10000000]; int bfs (int x,int k)
{
int s = 0,e = 0; q[s].num = x;
q[s++].t = 0;
vis[x] = 1;
while (s != e)
{
struct node tmp = q[e++];
e %= LEN; if (tmp.num == k)
return tmp.t; if (!vis[tmp.num + 1] && tmp.num <= k)
{
q[s].num = tmp.num + 1;
q[s++].t = tmp.t +1;
s %= LEN;
vis[tmp.num + 1] = 1;
} if (!vis[tmp.num - 1] && tmp.num - 1 >= 0)
{
q[s].num = tmp.num - 1;
q[s++].t = tmp.t +1;
s %= LEN;
vis[tmp.num - 1] = 1;
} if (!vis[tmp.num * 2] && tmp.num <= k)
{
q[s].num = tmp.num * 2;
q[s++].t = tmp.t +1;
s %= LEN;
vis[tmp.num * 2] = 1;
}
} return -1;
} int main()
{
int x,k; while (~scanf ("%d%d",&x,&k))
{
int ans = bfs (x,k); printf ("%d\n",ans);
}
return 0;
}