HDU 2717 Catch That Cow

http://acm.hdu.edu.cn/showPRoblem.php?pid=2717

  第一个bfs的题 用到队列的知识 上篇中有队列使用的方法。

  思路比较简单   在每一个结点都有三种情况  最先到达终端的一定是用时最短的  

  一定要注意边界和去重问题  因为边界没处理好  WA 了好多次  ！！！ 注意边界处理！！！

#include <stdio.h>#include <queue>#include <string.h>using namespace std;int N,K;int vis[200010] ; struct node{    int n;    int step;//步数   也可代表是第几层结点 };int judge(int n){    if (n>100000||n<0||vis[n])//边界  vis[] 数组用来去掉重复的结点         return 0;    return 1;}void bfs(int t){        queue<node>Q;    node x,y;    x.n=t;    x.step=0;    vis[x.n]=1;//将访问过的结点标记为 1     Q.push(x);        while (!Q.empty()){        y=Q.front();        Q.pop();        if (y.n==K)//到达终端  结束搜索 		{            printf ("%d/n",y.step);            break;        }                node z;        //三种情况全部入队         z.n=y.n+1;//  +1的情况         if (judge(z.n)){            z.step=y.step+1;            vis[z.n]=1;//将访问过的结点标记为 1             Q.push(z);        }                        z.n=y.n-1;//  -1的情况         if (judge(z.n)){            z.step=y.step+1;            vis[z.n]=1;//将访问过的结点标记为 1             Q.push(z);        }                         z.n=y.n*2;// *2的情况         if (judge(z.n)){            z.step=y.step+1;            vis[z.n]=1;//将访问过的结点标记为 1             Q.push(z);        }        }    }int main (){    while (scanf ("%d%d",&N,&K)!=EOF){        memset(vis,0,sizeof(vis));//所有结点初始化为  未被标记         bfs(N); //传递起始位置     }    return 0;}