学步园

Eight Puzzle
   做了此题，更加深深感觉到了咱们oj数据的强大威力，在其他oj绝对能过的到了这里TLE（其实发生过很多回了）
   此题运用广度优先搜索+hash（康托展开）
   此题的常规做法是开一个9*9*9*9*9*9*9*9*9 的数组用于存储状态 但是这是极大的浪费事实上也是不可能的
   超内存的
   因此就要用到hash来进行处理，运用康拓展开来实现的原理是一个数的阶乘（9!）可以表示成（0-----8！*7 + 7！*6 + 6！*5 + 1！*0）
   此区间的数一一对应，于是只开一个9！的数组就行了 空间是足够的
   还有一个十分重要的剪枝也许在其他oj不需要但是在我们oj是必不可少的，就是因为有多组数据，在广度搜素过程中因为一次有30多万的状态
  多搜几次就超时了，怎么办呢？
  逆着搜，只搜索一遍  然后记录下从目标状态到初始状态的最短路径，然后只是需要O（1）的时间的复杂度就可以完成了。

#include<cstdio>
#include<cstring>


struct node
{
    int state[3][3];
    int step;
}que[362881];
int hash[362881][2];
int a[9];
int b[3][3];
char str[20];
char map[3][3];
int dir[4][2]={1,0,-1,0,0,-1,0,1};
int f[9]={1,1,2,6,24,120,720,5040,40320};


int hash_res()
{
   int k = 0;
   int res=0,i,j;
   for(i=0;i<3;i++)
     for(j=0;j<3;j++)
      a[k++]=b[i][j];
   for(int i=0;i<9;i++)
   {    int num=0;
        for(int j=0;j<i;j++)
          if(a[j]>a[i]) num++;
        res+=f[i]*num;
   }
   return res;
}
void bfs()
{
   int front =0,rear =0,i,j;
   memset(hash,0,sizeof(hash));
   for(i=0;i<3;i++)
     for(j=0;j<3;j++)
     {
       if(map[i][j]=='x')
       que[rear].state[i][j]=9;
       else
       que[rear].state[i][j]=map[i][j]-'0';
     }


   for(i=0;i<3;i++)
     for(j=0;j<3;j++)
     b[i][j]=que[rear].state[i][j];


   hash[hash_res()][0]=1;
   hash[hash_res()][1]=0;
   que[rear].step = 0;
   rear++;


 while(front<rear)
   {
      int x,y;
      node head = que[front];
      front++;


      for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
          b[i][j]=head.state[i][j];
          if(b[i][j]==9)
          {
            x = i; y = j;
          }
        }


       for(i=0;i<4;i++)
        {
          int ii,jj;
          int nx = x + dir[i][0];
          int ny = y + dir[i][1];
          if(nx>=0&&ny>=0&&nx<3&&ny<3)
          {
              int temp;
              temp = b[nx][ny];
              b[nx][ny] = b[x][y];
              b[x][y] = temp;


              if(hash[hash_res()][0]==0)
               {
                for(ii=0;ii<3;ii++)
                  for(jj=0;jj<3;jj++)
                  que[rear].state[ii][jj]=b[ii][jj];


                  hash[hash_res()][0]=1;
                  hash[hash_res()][1]=head.step+1;


                  que[rear].step=head.step+1;
                  rear++;
               }


             temp = b[nx][ny];
             b[nx][ny] = b[x][y];
             b[x][y] = temp;
         }
       }
   }
}
int main()
{
    map[0][0]='1';
    map[0][1]='2';
    map[0][2]='3';
    map[1][0]='4';
    map[1][1]='5';
    map[1][2]='6';
    map[2][0]='7';
    map[2][1]='8';
    map[2][2]='9';
    bfs();
    while(gets(str))
    {
       int m = 0;
       for(int i=0;i<3;i++)
         for(int j =0;j<3;j++)
         {
             b[i][j]=str[m]-'0';
             m+=2;
         }
         int res =hash_res();
         if(res !=0&&hash[hash_res()][1]!=0)
         printf("%d\n",hash[hash_res()][1]);
         else if(res==0)
         printf("%d\n",hash[hash_res()][1]);
         else printf("unsolvable\n");
    }
    return 0;
}