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