Catch That Cow（农夫和牛）（BFS入门）（详解）

题目：

题目大意：

输入n和k表示农夫和牛的位置，n和k在区间【0，100000】间
农夫有三种方式进行移动，每种方式需要的时间相同，都是一分钟
1.向前移动一米（+1）
2.向后移动一米（-1）
3.移动到2*n（移动到二倍农夫当前米数）
牛不动
求农夫走到牛所在位置的最短时间（分钟）并输出。

代码：

#include <cstdio>
#include<queue>
#include<cstring>
#define position 100005
using namespace std;
int n,k;
struct num//定义结构体表示每一个位置
{
    int x;//位置坐标
    int step;//走到这一步的步数（我们将时间转换为步数理解，每一步需要一分钟）
};
bool visit[position];//标记，判断是否走过
void bfs()
{
    queue<num> steps;//定义队列存储位置
    //BFS是宽度优先，有时候需要队列（先进先出）
    num start,now,next;//start表示起点，now表示当前的位置，next表示下一步的位置
    memset(visit,false,sizeof(visit));//初始化标记（都为false表示未走过）
    start.x=n;//初始化起点
    start.step=0;
    steps.push(start);//起点入队
    visit[start.x]=true;//标记起点（表示走过）
    while(!steps.empty())
    {
        now=steps.front();//取队列首元素表示当前位置
        steps.pop();//首元素出列
        if(now.x==k)//如果当前位置就是牛的位置（得到结果）输出步数，退出调用函数
        {
            printf("%d\n",now.step);
            return;
        }
        for(int i=0;i<3;i++)//对三种走的方式分别进行尝试
        {
            if(i==0)
                next.x=now.x+1;
            else if(i==1)
                next.x=now.x-1;
            else if(i==2)
                next.x=now.x*2;
            if(next.x>=0&&next.x<position&&!visit[next.x])//如果在位置范围内（0~100000）且未被标记（未走过）
            //假如被标记则代表前面用了更少的步数到达这一点，根据题目要求求最少的步数（时间），所以不需要进行这一步了
            {
                visit[next.x]=true;//标记这个位置（表示走过了）
                next.step=now.step+1;//步数加一
                steps.push(next);//入队
            }
        }
    }
}
int main()
{
    scanf("%d %d",&n,&k);
    bfs();
    return 0;
}