问题描述：
农夫John的一头牛逃跑了，他想要将逃跑的牛找回来。现假设农夫John和牛的位置都在一条直线上，农夫John的初始位置为N（0≤N≤100,000），牛的初始位置为K（0≤K≤100,000）。农夫John有两种移动方式：行走和传送。
行走：农夫John可以从当前位置X移动到X-1或X+1，花费时间1分钟。
传送：农夫John可以从当前位置X传送到2×X，花费时间1分钟。
现假设牛逃跑后的位置一直保持不变，请编写一个程序，计算农夫John找到牛的最短时间。
输入格式：输入N和K（中间用一个空格间隔）。
输出格式：输出最短的寻找时间，单位分钟。
方法：
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
分析：
首先，每一步（节点）都有两个信息要素：当前距离和时间，故声明一个结构体
struct S
{int time;int add;
}其次，bfs多使用队列（queue）进行各个分支的遍历，队列：先进先出
queue<S> q;首先第一个节点是：
S s0={0,n}; //cin>>n>>k;bfs的关键思路是遍历队列中的每个节点，进行i(i=3)次操作，生成i个新的节点，继续放在队列中。（每次操作需要pop当前遍历到的节点，观察是否达到目标，如果有，跳出当前操作，没有就做对应的操作，生成对应三个操作后的新节点放入队列中）
因为每一层操作都是time+1，整个搜索过程是按照一层一层搜索的，所以只要当前没有结束搜索，那么此时这个一定是最快的方法（之一）直接退出搜索就好了：输出最优解时间。
while(!q.empty()) //队列不空
{0.取出队列首元素 S s=q.front();1.判断是否达到目标？跳出搜索：进行三种操作并生成对应节点，放入队列2.三个操作（1） (s.add+1) 创造新节点s1={s.time+1,a.add+1},放入队列（2） (s.add-1) 创造新节点s1={s.time+1,a.add-1},放入队列（3） (s.add*2) 创造新节点s1={s.time+1,a.add*2},放入队列
}
优化操作：进行剪枝
剪枝情况1：创建一个flag数组，登记当前add情况有没有在此之前就搜索过（如果之前有，那么当前搜索状况一定不是最优的，没必要按照当前这条路继续搜索下去）——搜索过就不搜索了
剪枝情况2：如果当前add<=0 则不需要进行add-1和add*2的操作——不进行无意义的操作
剪枝情况3：如果add>k 则不进行add+1和add*2的操作——同上
特殊情况：牛在农夫前面（n>k），只能进行操作（2），直接输出结果即可（但是由于剪枝的存在，这样的特殊情况特殊处理不会带来特别大的优化）
while(!q.empty()) //队列不空
{0.取出队列首元素 S s=q.front();1.判断是否搜索过（flag）？如果没有：{2.判断是否达到目标？如果有：跳出搜索，输出最短时间。否则：{3.判断是否add<=0?只进行操作（1）判断是否add>k?只进行操作（2）否则：进行三个操作}4.将flag置为1（已搜索）}
}代码实现：
#include<iostream>
#include<queue>
using namespace std;struct S{int time;//所用时间int add;//当前位置
};int flag[200000] = {0};//标识对应位置是否求过
queue<S> q;//队列存储当前操作节点
int k;//全局对照量（目标距离k）void bfs()
{while(!q.empty())//队列不为空继续搜索{S s = q.front();//头结点cout<<"现在遍历节点为：add="<<s.add<<" time="<<s.time<<endl;q.pop();//删除头结点if(flag[s.add]==0)//（剪枝1）{if(s.add==k)//农夫的位置和牛的位置一样，抓到了{cout << "农夫的位置和牛的位置相同（抓到牛了） 花费时间："<<s.time << endl;break;//跳出while循环}//三个操作S next;//创建新节点next.time = s.time + 1;//所有操作都是time+1if(s.add>k)//(剪枝2){next.add = s.add - 1;q.push(next);cout<<"新节点入队： add="<<next.add<<" time="<<next.time<<endl;}else if(s.add<=0){next.add = s.add + 1;q.push(next);cout<<"新节点入队： add="<<next.add<<" time="<<next.time<<endl;}else{next.add = s.add - 1;q.push(next);cout<<"新节点入队： add="<<next.add<<" time="<<next.time<<endl;next.add = s.add + 1;q.push(next);cout<<"新节点入队： add="<<next.add<<" time="<<next.time<<endl;next.add = s.add * 2;q.push(next);cout<<"新节点入队： add="<<next.add<<" time="<<next.time<<endl;}flag[s.add] = 1;//标识这个位置计算过了}}}int main()
{int n;//农夫的位置cin >> n >> k;S s={0,n};q.push(s);bfs();//进行宽度优先搜索return 0;
}
