POJ 3278 Catch That Cow BFS（第一题）

【题意简述】：一个农夫和一头牛在同一坐标轴上，且已知坐标，农夫可以从坐标是x的点移动到x-1、x+1和x*2，求最少几步可以抓到牛。

【思路】：这是我的第一道有关BFS的搜索题！(BFS常用于解决最优可行解问题！而且通常应用队列这一数据结构)

我小心翼翼去完成这道经典的题，所以参考了，很多资料。精华部分，我都摘录下来至此：

我们已经知道此题给我我们一个起点和一个终点，每个点都能到达的状态是x-1、x+1、x*2，对于每一个状态都可以到达3个子状态，因此从起点开始，第二层状态就有3个，第三层就有9个……，这样下去，直到搜索到终点结束，那么求出的步数就可以达到最小！

因为对于相同层的状态，所需的步数是相同的，而且对于层与层之间的状态来说，先搜索完的前一层的所有状态才开始下一层的搜索。也就是说前一个节点的步数一定小于等于后一个节点的步数。所以当第一次到达终点的时候，就得到了最短的路径。。但是如果这样硬搜的话便会超时，所以 又是剪枝！！剪枝是很重要的，剪枝这个东西就是靠多积累！多做题！多感受！

// 1592K 47Ms
#include
  
   
#include
   
     #include
    
      using namespace std; struct node // 构造节点！！ { int num; int count; node(){} node(int n,int c) { num = n; count = c; } }; node queue[1000000]; bool visit[200010]; int bfs(int n,int k) { if(n ==k ) return 0; //此处注意，是个特例！ node n0(n,0); memset(visit,false,sizeof(visit)); int top = 0,end = 0; queue[end++] = n0; visit[n] = true; while(top != end) { node temp = queue[top++]; if(top >= 1000000) top = 0; node n1(temp.num - 1,temp.count+1); node n2(temp.num + 1,temp.count+1); node n3(temp.num * 2,temp.count+1); if(n1.num == k) return n1.count; if(n2.num == k) return n2.count; if(n3.num == k) return n3.count; if(n1.num<150005&n1.num >= 0&&!visit[n1.num]){ // 注意剪枝条件！，不然很可能TLE // 当超过150005时就不用考虑了！！ // 当小于0时也不必考虑 // 已经搜索过的节点也不必考虑 // 以上这些就是剪枝部分！！ queue[end++] = n1; if(end >= 1000000) end = 0; //循环队列！ visit[n1.num] = true; } if(n2.num < 150005 && n2.num >= 0 && !visit[n2.num]){ queue[end++] = n2; if(end >=1000000) end = 0; visit[n2.num] = true; } if(n3.num <150005&&n3.num >= 0&&!visit[n3.num]) { queue[end++] = n3; if(end>=1000000) end = 0; visit[n3.num] = true; } } } int main() { int n,k; cin>>n>>k; cout<