首页 > 代码库 > poj3278(bfs)

poj3278(bfs)

 

题目链接:http://poj.org/problem?id=3278

分析:广搜,每次三种情况枚举一下,太水不多说了。

 

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;struct node{    int x,step;    bool operator<(const node a)const    {        return step>a.step;    }};priority_queue<node>que;int vis[N];int judge(int x){    return x>=0&&x<=100000;}node make_node(int a,int b){    node temp;    temp.x=a;temp.step=b;    return temp;}int main(){    int n,k;    while(scanf("%d%d",&n,&k)>0)    {        memset(vis,0,sizeof(vis));        while(!que.empty())que.pop();        que.push(make_node(n,0));        vis[n]=1;        int ans=0;        while(!que.empty())        {            node now=que.top();            que.pop();            int x=now.x;//printf("%d %d\n",now.x,now.step);            if(x==k)            {                ans=now.step;                break;            }            if(judge(x+1)&&!vis[x+1])            {                vis[x+1]=1;que.push(make_node(x+1,now.step+1));            }            if(judge(x-1)&&!vis[x-1])            {                vis[x-1]=1;que.push(make_node(x-1,now.step+1));            }            if(judge(2*x)&&!vis[x*2])            {                vis[x*2]=1;que.push(make_node(2*x,now.step+1));            }        }        printf("%d\n",ans);    }}
View Code

 

poj3278(bfs)