本文主要是介绍poj 3278 bfs,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
如图:http://poj.org/problem?id=3278
广搜
#include<iostream>
using namespace std;
#include<queue>
int visited[100004];
struct node
{
int num;
int count;
node(int n,int m)
{
num=n;
count=m;
}
};
queue<node>QUE;
int bfs(int n,int k)
{
if(n==k) return 0;
node n0(n,0);
memset(visited,0,sizeof(visited));
QUE.push(n0);
visited[n]=1;
while(!QUE.empty())
{
node temp=QUE.front();
QUE.pop();
node n1(temp.num-1,temp.count+1);
node n2(temp.num+1,temp.count+1);
node n3(temp.num*2,temp.count+1);
if(n1.num==k) return n1.count;
if(n2.num==k) return n2.count;
if(n3.num==k) return n3.count;
if(n1.num>0&&n1.num<100005&&visited[n1.num]==0)
{
QUE.push(n1);
visited[n1.num]=1;
}
if(n2.num>0&&n2.num<100005&&visited[n2.num]==0)
{
QUE.push(n2);
visited[n2.num]=1;
}
if(n3.num>0&&n3.num<100005&&visited[n3.num]==0)
{
QUE.push(n3);
visited[n3.num]=1;
}
}
}
int main()
{
int n,k;
while(~scanf("%d %d",&n,&k))
{
printf("%d\n",bfs(n,k));
}
}
这篇关于poj 3278 bfs的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!