UVA_704

    以前即使八数码问题也没有用双向BFS，但这次状态数太多了，于是不得不使用双向BFS了。

#include
     
       #include
      
        #include
       
         #define HASH 10000003 int head1[HASH],next1[100000],head2[HASH],next2[100000]; int st[200000][21],dis[200000],front,rear; int fa[200000],flag[200000],dir,ans,mid; int target[21]={
    0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0}; int hash(int *a) {
    int i,v=0; for(i=0;i<21;i++)         v=(v*10+a[i])%HASH; return v; } int insert(int s) {
    int i,h;     h=hash(st[s]); if(!dir)     {
    for(i=head1[h];i!=-1;i=next1[i]) if(memcmp(st[s],st[i],sizeof(st[i]))==0) break; if(i==-1)         {
                next1[s]=head1[h];             head1[h]=s; return 1;         }     } else     {
    for(i=head2[h];i!=-1;i=next2[i]) if(memcmp(st[s],st[i],sizeof(st[i]))==0) break; if(i==-1)         {
                next2[s]=head2[h];             head2[h]=s; return 1;         }     } return 0; } int search(int s) {
    int i,h;     h=hash(st[s]); for(i=head1[h];i!=-1;i=next1[i]) if(memcmp(st[s],st[i],sizeof(st[i]))==0) break; if(i==-1) return 0; else return i; } void bfs() {
    int i,p,temp[2]; while(front
        
         1;i--)                     st[rear][i]=st[rear][i-2];                     st[rear][1]=temp[1];                     st[rear][0]=temp[0]; if(insert(rear))                     {
                            fa[rear]=front;                         flag[rear]=p;                         dis[rear]=dis[front]+1;                         rear++;                     }                 } else if(p==2)                 {
                        memcpy(st[rear],st[front],sizeof(st[front]));                     temp[0]=st[front][9];                     temp[1]=st[front][10]; for(i=9;i<19;i++)                         st[rear][i]=st[rear][i+2];                     st[rear][19]=temp[0];                     st[rear][20]=temp[1]; if(insert(rear))                     {
                            fa[rear]=front;                         flag[rear]=p;                         dis[rear]=dis[front]+1;                         rear++;                     }                 } else if(p==3)                 {
                        memcpy(st[rear],st[front],sizeof(st[front]));                     temp[0]=st[front][0];                     temp[1]=st[front][1]; for(i=0;i<10;i++)                         st[rear][i]=st[rear][i+2];                     st[rear][10]=temp[0];                     st[rear][11]=temp[1]; if(insert(rear))                     {
                            fa[rear]=front;                         flag[rear]=p;                         dis[rear]=dis[front]+1;                         rear++;                     }                 } else                 {
                        memcpy(st[rear],st[front],sizeof(st[front]));                     temp[0]=st[front][19];                     temp[1]=st[front][20]; for(i=20;i>10;i--)                         st[rear][i]=st[rear][i-2];                     st[rear][9]=temp[0];                     st[rear][10]=temp[1]; if(insert(rear))                     {
                            fa[rear]=front;                         flag[rear]=p;                         dis[rear]=dis[front]+1;                         rear++;                     }                 }             }         front++;     } } void printpath1(int a) {
    if(fa[a]!=-1)         printpath1(fa[a]); else return;     printf("%d",flag[a]); } void printpath2(int a) {
    if(fa[a]!=-1)     {
    if(flag[a]>2)             printf("%d",flag[a]-2); else             printf("%d",flag[a]+2);         printpath2(fa[a]);     } else return; } int main() {
    int i,j,k,p,t;     scanf("%d",&t); while(t--)     {
    for(i=0;i<24;i++)         {
                scanf("%d",&k); if(i<21)                 st[0][i]=k;         }         front=rear=0;         fa[rear]=-1;         memset(head1,-1,sizeof(head1));         dir=0;         insert(rear);         dis[rear]=0;         rear++;         bfs(); if(front!=rear)         {
    if(ans==0)                 printf("PUZZLE ALREADY SOLVED\n"); else             {
                    printpath1(front);                 printf("\n");             } continue;         }         memcpy(st[rear],target,sizeof(target));         front=rear;         fa[rear]=-1;         dir=1;         memset(head2,-1,sizeof(head2));         insert(rear);         dis[rear]=0;         rear++;         bfs(); if(front!=rear)         {
                printpath1(mid);             printpath2(front);             printf("\n");         } else             printf("NO SOLUTION WAS FOUND IN 16 STEPS\n");     } return 0;    }