BFS_catch the cow

实质就是遍历所有可能的点(踩点)，点入队，先入先出，形成一棵枝繁叶茂的树，谁先到达目的点，谁就胜利，输出此条路径累计的时间数。

所以要记录每一次踩点的累计值step.

另外，一定要注意的是，已入队的点千万不要重复入队，因为这毫无意义(会重复进行此点此前的操作)

代码如下：

解法一：

#include <iostream>
#include <fstream>
#include <cstdio>
#include <queue>
#include <memory.h>
#define MAX 100005
using namespace std;
queue<int> q;
int step[MAX]; //跟随数组，记录步数
bool visit[MAX];
int n,k;
int next,head;
/*一般情况下是不需要将出队后的点“涂黑”的 */
/*但是入队时避免重复入队，必须先标记，表示已被发现的点*/
int bfs()
{
q.push(n);
step[n]=0;
visit[n]=1;
while(!q.empty())
{
head=q.front();
q.pop( );
//分三个方向BFS
for(int i=0; i<3 ;i++)
{
if(i==0) next=head-1;
//以下这三种情况都相当于是head的邻接顶点
else if(i==1) next=head+1;
else
next=head*2;
if(next>k || next< n )
continue;
//必须先判断，不然会RE，数组越界了
if(!visit[next])
//点入队
{
q.push(next);
step[next]=step[head]+1;
visit[next]=1;
//避免重复入队
}
if(next==k)
return step[next];
}
}
return -1;
}
int main()
{
memset(visit,0,sizeof(visit));
scanf("%ld%ld",&n,&k);
if(n>=k)
{
printf("%d",n-k);
}
else
{
printf("%d",bfs());
}
return 0;
}

解法二：

#include<iostream>
using namespace std;
const int large=200030;
typedef class
{
public:
int x;
//当前点
int step;
//当前点的累积步数
}pos;
int n,k;
bool vist[large];
//数组较大，必须开为全局数组，不然肯定RE
pos queue[large];
void BFS(void)
{
int head,tail;
queue[head=tail=0].x=n;
queue[tail++].step=0;
vist[n]=true;
while(head<tail)
{
pos w=queue[head++];
if(w.x==k)
{
cout<<w.step<<endl;
break;
}
if(w.x-1>=0 && !vist[w.x-1])
//w.x-1>=0
是剪枝
{
vist[w.x-1]=true;
queue[tail].x=w.x-1;
queue[tail++].step=w.step+1;
}
if(w.x<=k && !vist[w.x+1])
//w.x<=k
是剪枝
{
vist[w.x+1]=true;
queue[tail].x=w.x+1;
queue[tail++].step=w.step+1;
}
if(w.x<=k && !vist[2*w.x])
//w.x<=k
是剪枝
{
vist[2*w.x]=true;
queue[tail].x=2*w.x;
queue[tail++].step=w.step+1;
}
}
return;
}
int main(void)
{
while(cin>>n>>k)
{
memset(vist,false,sizeof(vist));
BFS();
}
return 0;
}

最后

以上就是真实便当为你收集整理的BFS_catch the cow的全部内容，希望文章能够帮你解决BFS_catch the cow所遇到的程序开发问题。

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