专解最小层次广度优先搜索BFS

广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。
注意：
1、在遍历过程中需要一个访问标志数组；
2、为了顺次访问路径长度为2、3、。。。的顶点，需附设队列以存储已经被访问的路径长度为1,2,3,...的顶点。

现在写一下关于我对队列的心得体会：

 

#include<queue>

1.queue<int> Q; //这个就是建立一个队列，名字叫Q，队列里的所有元素都是int整型；

2.Q.push(a); //这个就是将一个元素a，push进去排队；

3.b=Q.front(); //这个就是队列Q的排最前第一个的元素的值赋给b；

4.Q.pop(); //这个就是将排第一的元素移出队列，第二个的自然跟上；

5.Q.empty(); //这个就是判断队列Q是否为空，如果空就是1，不空就是0。

memset(flag,0,sizeof(flag))//将数组置为0;

 

比如：

题目大意：FJ的牛跑了，FJ想在最短的时间内把他追回来。如果FJ在格子 i 则FJ可以在一分钟内移动到 i -1，i+1(跑步)和 i*2(乘飞机) 三个格子中的任意一个，每组数据给出

n FJ当前位置 

k cow所在位置（cow是不会跑的）

求FJ最少需要多少时间才能把逃跑了的cow追回来

按广度优先，为什么呢，因为我们从三个方向广度搜索的话，路径是不断增加，那么只要一搜到目标，就可以输出，因为无论从哪一个分支搜索到，它们都是在同一层，即为所求的最小步数；

#include<iostream>
#include<queue>
using namespace std;
int line[100001];//可以作为标志，并且存储增量
int n,k;

void BFS()
{
    queue<int>q;//存储坐标
    q.push(n);
    line[n]=1;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        if(t==k)
            break;
        int next=t-1;//左
        if(next>=0 && !line[next])
        {
            q.push(next);
            line[next]=line[t]+1;
        }

        next=t+1;//右
        if(!line[next])
        {
            q.push(next);
            line[next]=line[t]+1;
        }

        next=t*2;//向右飞跃
        if(next<=100000 && !line[next]&& (next-k)<(k-t))// 两倍的距离要少于直接距离
        {
            q.push(next);
            line[next]=line[t]+1;
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(line,0,sizeof(line));
        if(n>=k)
            printf("%d\n",n-k);
        else
        {
            BFS();
            printf("%d\n",line[k]-1);
        }
    }
    return 0;
}