Source Code

Problem: 1077  User: yzhw9981 
Memory: 9076K  Time: 969MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
char data[11];
int top=-1,last=0,start=0;
char stack[500000];
bool hash[500000];
int jie[10];
struct point
{
   int layer;
   int q;
   char dir;
   point* last;
   char queue[11];
};
bool cmp1(const point *a,const point *b)
{
     return a->q+a->layer>b->q+b->layer;
}
class heap
{
private:
      vector<point*> head;
public:
      void add(point *t)
      {
           head.push_back(t);
           push_heap(head.begin(),head.end(),cmp1);
      }
      point *pop()
      {
          pop_heap(head.begin(),head.end(),cmp1);
          point *res=head.back();
          head.pop_back();
          return res;
      }
      int size()
      {
          return head.size();
      }
};
heap refer;
int match(int a,int b,char queue[])
{
   int total=0;
   if(queue[a]!=a) total++;
   if(queue[b]!=b) total++;
   return total;
}
void puthash(char h[])
{
     int total=0;
    for(int i=1;i<=9;i++)    
    {        
         int num=0;        
         for(int j=1;j<i;j++)            
           if(h[j]>h[i])  
              num++;        
         total+=jie[i-1]*num;    
    }   
     hash[total]=1;
}
bool hashash(char h[])
{
     int total=0;
    for(int i=1;i<=9;i++)    
    {        
         int num=0;        
         for(int j=1;j<i;j++)            
           if(h[j]>h[i])  
              num++;        
         total+=jie[i-1]*num;    
    }  
     if(hash[total]) return 1;
     else return 0;
}
point* det()
{
    int rc=0;
    while(refer.size())
    {
      point *t=refer.pop();
      if(t->q==0) 
         {
           
            return t;
            }
      if(t->queue[0]+3<=9)//down
      {
        point *pos=new point;
        strcpy(pos->queue,t->queue);
        pos->queue[t->queue[0]]=t->queue[t->queue[0]+3];
        pos->queue[t->queue[0]+3]=t->queue[t->queue[0]];
        pos->queue[0]=pos->queue[0]+3;
        if(hashash(pos->queue))
        {
         delete pos;
        }
        else
        {
          pos->q=t->q-match(t->queue[0],t->queue[0]+3,t->queue)+match(t->queue[0],t->queue[0]+3,pos->queue);
          pos->layer=t->layer+1;
          pos->last=t;
          pos->dir='d';
          puthash(pos->queue);
          refer.add(pos);
        
        }
      }
      if(t->queue[0]-3>=1)//up
      {
        point *pos=new point;
        strcpy(pos->queue,t->queue);
        pos->queue[t->queue[0]]=t->queue[t->queue[0]-3];
        pos->queue[t->queue[0]-3]=t->queue[t->queue[0]];
        pos->queue[0]=pos->queue[0]-3;
        if(hashash(pos->queue))
        {
         delete pos;
        }
        else
        {
          pos->q=t->q-match(t->queue[0],t->queue[0]-3,t->queue)+match(t->queue[0],t->queue[0]-3,pos->queue);
          pos->layer=t->layer+1;
          pos->last=t;
          pos->dir='u';
          puthash(pos->queue);
          refer.add(pos);

        }                       
      }
      if(t->queue[0]%3==0||t->queue[0]%3==2)//left
      {
        point *pos=new point;
        strcpy(pos->queue,t->queue);
        pos->queue[t->queue[0]]=t->queue[t->queue[0]-1];
        pos->queue[t->queue[0]-1]=t->queue[t->queue[0]];
        pos->queue[0]=pos->queue[0]-1;
        if(hashash(pos->queue))
        {
         delete pos;
        }
        else
        {
          pos->q=t->q-match(t->queue[0],t->queue[0]-1,t->queue)+match(t->queue[0],t->queue[0]-1,pos->queue);
          pos->layer=t->layer+1;
          pos->last=t;
          pos->dir='l';
          puthash(pos->queue);
          refer.add(pos);
 
        }
      }
      if(t->queue[0]%3==1||t->queue[0]%3==2)//right
      {
        point *pos=new point;
        strcpy(pos->queue,t->queue);
        pos->queue[t->queue[0]]=t->queue[t->queue[0]+1];
        pos->queue[t->queue[0]+1]=t->queue[t->queue[0]];
        pos->queue[0]=pos->queue[0]+1;
        if(hashash(pos->queue))
        {
         delete pos;
        }
        else
        {
          pos->q=t->q-match(t->queue[0],t->queue[0]+1,t->queue)+match(t->queue[0],t->queue[0]+1,pos->queue);
          pos->layer=t->layer+1;
          pos->last=t;
          pos->dir='r';
          puthash(pos->queue);
          refer.add(pos);
        }
      }
    }
    return NULL;
}


int main()
{
    int q=0;
    memset(hash,0,sizeof(hash));
    point *s=new point;
    jie[0]=jie[1]=1;
    for(int i=2;i<=9;i++) jie[i]=jie[i-1]*i;
    for(int i=1;i<=9;i++)
    {
       char temp;
       cin>>temp;
       if(temp=='x')
       {
        data[0]=i;
        data[i]=9;
       }
       else data[i]=temp-48;
    }
    data[10]='\0';
    for(int i=1;i<=9;i++) 
       if(data[i]!=i) q++;
    s->dir='N';
    s->layer=0;
    s->last=NULL;
    s->q=q;
    strcpy(s->queue,data);
    refer.add(s);
    puthash(data);
    if(s=det())
    {
      while(s)
      {
       stack[++top]=s->dir;
       s=s->last;
      }
      top--;
      while(top!=-1) cout<<stack[top--];
      cout<<endl;
    }
    else cout<<"unsolvable"<<endl;
    system("pause");
}
     
      
       

• Re:A* 900多MS AC汗死我。。我用的是步数+不相同格数启发的，怎么会这么慢啊，大牛帮忙看看，附代码 (48) sdfox 2009-04-14 16:20:17