BFS-Catch That Cow POJ - 3278（线性BFS模板题）

Catch That Cow POJ - 3278（线性BFS模板题）

蓝桥杯校赛打得太菜了555555555
菜得实在不忍心去睡来切一道水题
一道模板题还是RE到头大，真的是菜比啊

题目如下：

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

• Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
• Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

①、写于2019-12-02

题目大意：

在一个一维数轴上给出起点位置N和终点位置K，每次有三种移动的选择：

1. 从位置X移动到X-1
2. 从位置X移动到X+1
3. 从位置X移动到2X

每次移动将花费一分钟，问最少将花费几分钟。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N,K;
struct pos{
int p,level;//p为当前位置，level为层次
};
pos P;
queue<pos>Q;//RE了很多次还是把队列拿了出来（其实问题不是出这里，但是尽量还是定义全局变量比较稳妥）
bool vis[100005];//标记走过的点，不必再走一遍，优化1
void bfs(pos p)
{
Q.push(P);
vis[P.p]=true;
P.level=0;
while(!Q.empty())
{
pos tmp=Q.front();//用一个临时变量及时更新当前操作的点
if(tmp.p==K) {cout<<tmp.level;return;}
Q.pop();
pos tmp1;//临时变量将新点入队
if(tmp.p>=1&&!vis[tmp.p-1])//防止数组访问越界
{
vis[tmp.p-1]=true;
tmp1.level=tmp.level+1;
tmp1.p=tmp.p-1;
Q.push(tmp1);
}
if(tmp.p<K&&!vis[tmp.p+1])//这里tmp.p<K可省，但是一个可以优化的点，因为如果当前位置比K大，那么加1和乘2显然不是最优解
{
vis[tmp.p+1]=true;
tmp1.level=tmp.level+1;
tmp1.p=tmp.p+1;
Q.push(tmp1);
}
if(tmp.p<K&&tmp.p<=50000&&!vis[tmp.p*2])//！！！这里tmp.p<=50000是RE了十几发的根本原因，一开始写的N<=50000(太粗心了！！)，避免访问越界
{
vis[tmp.p*2]=true;
tmp1.level=tmp.level+1;
tmp1.p=tmp.p*2;
Q.push(tmp1);
}
}
}
int main()
{
memset(vis,false,sizeof(vis));
cin>>P.p>>K;
bfs(P);
return 0;
}

还是简单总结一下本题：

1. 尽量把变量定义在外部
2. bfs进入while的第一步应该要及时更新起点（以当前点进行继续操作）
3. vis标记减少无效搜索
4. RE的几个原因： (一般是程序在运行期间执行了非法的操作造成的）

• ACCESS_VIOLATION 您的程序想从一些非法的地址空间读取或搜索向其中写入内容。一般例如指针、数组下标越界都会造成这个错误的。
• ARRAY_BOUNDS_EXCEEDED 您的程序试图访问一个超出硬件支持范围的数组单元。
• FLOAT_DENORMAL_OPERAND 进行了一个非正常的浮点操作。一般是由于一个非正常的浮点数参与了浮点操作所引起的。
• FLOAT_DIVIDE_BY_ZERO 浮点数除法出现除数为零的异常。
• FLOAT_OVERFLOW 浮点溢出。要表示的数太大，超出了浮点数的表示范围。
• FLOAT_UNDERFLOW 浮点下溢。要表示的数太小，超出了浮点数的表示范围。
• INTEGER_DIVIDE_BY_ZERO 在进行整数除法的时候出现了除数为零的异常。
• INTEGER_OVERFLOW 整数溢出。要表示的数值太大，超出了整数变量的范围。
• STACK_OVERFLOW 栈溢出。一般是由于无限递归或者在函数里使用了太大的数组变量的原因。
  总之就是不要非法访问、不要溢出！！
  （完！

②、2020-6-9重写

$这里需要分析清楚几点：$

$假设终点是E，当前位置为X。$

$①、对乘2操作：当X介于(\frac{E}{2},E)之间时，先减小1再乘2，要优于先乘2再减小1。$

$理由：记\delta =X-\frac{E}{2}，若先减小到\frac{E}{2}，需要进行\delta +1步操作。$

$若先乘2，则2X-E=2\delta ，则共需要进行2\delta +1步操作。$

$因此，若2X>100000，我们就无需对其进行乘2操作。$

$②、对加1操作：仅在X<E的情况下进行。$

$③、对减1操作：只要X>0均可进行。因为可以先减小到\frac{E}{2}，再乘2。$

$所以并不是仅在X>E的情况下才能进行减小操作。$

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int s,e;
int q[N*2];
int d[N];
int bfs()
{
memset(d,-1,sizeof d);
int hh=0,tt=-1;
q[++tt]=s;
d[s]=0;
while(hh<=tt)
{
int t=q[hh++];
if(t==e) return d[e];
if(t<e && 2*t<=100000 && d[2*t]==-1)
{
q[++tt]=2*t;
d[2*t]=d[t]+1;
}
if(t<e && d[t+1]==-1)
{
q[++tt]=t+1;
d[t+1]=d[t]+1;
}
if(t>0 && d[t-1]==-1)
{
q[++tt]=t-1;
d[t-1]=d[t]+1;
}
}
}
int main()
{
cin>>s>>e;
cout<<bfs()<<endl;
return 0;
}

最后

以上就是合适嚓茶为你收集整理的BFS-Catch That Cow POJ - 3278（线性BFS模板题）的全部内容，希望文章能够帮你解决BFS-Catch That Cow POJ - 3278（线性BFS模板题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。