Catch That Cow poj 4001(抓住那头牛！） BFS（广度优先搜索）

题目链接

其实就是求最短路径问题，采用BFS即可。
AC代码如下：

#include <iostream>
#include <queue>
using namespace std;
const int maxn=2e5+5;
bool vis[maxn];
struct cow{
int pos;
int step;
cow(int xx,int s):pos(xx),step(s){};
};
void bfs(int n,int k)
{
queue <cow> q;
q.push(cow(n,0));
vis[n]=1; //标记该点已经走过了
while(!q.empty())
{
cow temp=q.front();
q.pop();
if(temp.pos==k){ //说明找到目标点了
cout<<temp.step<<endl;
return ;
}
else //说明还没有找到目标
{
int x=temp.pos;
if( x<k && !vis[x+1] && x+1<=maxn){
q.push(cow(x+1,temp.step+1)); vis[x+1]=!vis[x+1]; //进队列顺便标记该点
}
if( x<k && !vis[2*x] && 2*x<=maxn){
q.push(cow(2*x,temp.step+1)); vis[2*x]=!vis[2*x];
}
if( x-1>=0 && !vis[x-1] ){
q.push(cow(x-1,temp.step+1)); vis[x-1]=!vis[x-1];
}
}
}
}
int main()
{
int n,k;
cin>>n>>k;
bfs(n,k);
return 0;
}

最后

以上就是迷人御姐为你收集整理的Catch That Cow poj 4001(抓住那头牛！） BFS（广度优先搜索）的全部内容，希望文章能够帮你解决Catch That Cow poj 4001(抓住那头牛！） BFS（广度优先搜索）所遇到的程序开发问题。

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