poj3278（bfs）-白红宇

poj3278（bfs）

阅读量：6435 次

发布时间：2019-06-23

本文共 1197 字，大约阅读时间需要 3 分钟。

题目链接：

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

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #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
                
                 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); }}