纯BFS-->
#include <iostream>
#include <queue>
#include <algorithm>
#define NIL 99999999
using namespace std;

const int N = 100000, K = 100005;
struct P
{
       int p;
       int step;
}Q[K];
int ANS;
bool inqueue[K];

int bfs(int n, int k)
{
     int s = 0,e;
     if(n == k)
        return 0;      
     
     P now,next;
     now.p = n;
     now.step = 0;
     Q[s] = now;
     ANS = NIL;
     e = s + 1;
     inqueue[s] = true;
     while(s < e)
     {     
           now = Q[s++];
           next = now;
           next.p -= 1;
           next.step++;
           if(next.p == k)
           {
              ANS = min(ANS,next.step);         
           }
           else 
           if(next.step < ANS && next.p >= 0 && next.p <= N && !inqueue[next.p])
              Q[e++] = next,inqueue[next.p] = true;
           
           next = now;
           next.p += 1;
           next.step++;
           if(next.p == k)
           {
              ANS = min(ANS,next.step);
           }
           else 
           if(next.step < ANS && next.p >= 0 && next.p <= N && !inqueue[next.p])
              Q[e++] = next,inqueue[next.p] = true;
              
            next = now;
            next.p *= 2;
            next.step++;
            if(next.p == k)
            {
               ANS = min(ANS,next.step);
            }
            else 
            if(next.step < ANS && next.p >= 0 && next.p <= N && !inqueue[next.p])
               Q[e++] = next,inqueue[next.p] = true;               
     }
     return ANS; 
}

int main()
{
    int n,k;
    
    scanf("%d%d",&n,&k);
    printf("%d\n",bfs(n,k));     
 
    return 0;
}

• Re:还是得用堆诶 (9) crbtmac 2009-09-01 17:40:42