Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:还是得用堆诶

Posted by crbtmac at 2009-09-01 17:33:28 on Problem 1724
In Reply To:还是得用堆诶 Posted by:ljfljf2006 at 2009-09-01 17:07:08
纯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;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator