?

这几次都是每天的第一道题都挺顺利，然后第二道题一卡一天。 = =，今天的这道题7点40就出来了，不知道第二道题在下午7点能不能出来。0 0

先说说这道题目，大意是有个农夫要抓牛，已知牛的坐标，和农夫位置。而且农夫有三种移动方式，X + 1，X - 1，X * 2，问最少几步抓到牛。

开始认为很简单的，三方向的BFS就能顺利解决，然后在忘开标记的情况下直接广搜，果然TLE，在你计算出最少位置之前，牛早跑了。

然后反应过来开标记，来节约时间，然后发现居然RE了，估计是标记数组不够大，毕竟有一个方向的x * 2。

然后打算控制一下查找范围，因为当X到达某个范围之后，在变为K，肯定不会是最少路径。

比如，当X已经大于K了，再执行X + 1， X * 2,肯定不会最短的得到K，然后在判断标记的时候做了优化。

然后就过掉了。

我再去百度，看看有没有更好的方法，发现我这个方法就叫剪枝啊 = =。吓尿、

?

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #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 ,ans); } return 0; } 
     
    
   
  

?