POJ1077(Eight)

经典的8数码问题，不要求是最少步数。
View Code
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <queue>
  4 #define N 362881
  5 #define ABS(x) ((x)>0?(x):(-(x)))
  6 using namespace std;
  7 const int dx[4]={0,0,1,-1};
  8 const int dy[4]={1,-1,0,0};
  9 char DIR[4]={'r','l','d','u'};
 10 const int pow10[10]={1,10,100,1000,10000,
 11                       100000,1000000,10000000,
 12                       100000000,1000000000};
 13 typedef pair<int,int> node;
 14 priority_queue<node,vector<node>,greater<node> > pq;
 15 int s,t=123456780,tp=123456870;
 16 int tx[9]={2,0,0,0,1,1,1,2,2},ty[9]={2,0,1,2,0,1,2,0,1};
 17 int fact[9];
 18 int f[N],g[N],z[N],dir[N],p[N];
 19 char vis[N];
 20 int h(int k)
 21 {
 22   int i,x,y,ai,ret=0;
 23   for(x=0;x<3;x++)
 24   {
 25     for(y=0;y<3;y++)
 26     {
 27       i=8-3*x-y;
 28       ai=k/pow10[i]%10;
 29       ret+=ABS(tx[ai]-x)+ABS(ty[ai]-y);
 30     }
 31   }
 32   return ret;
 33 }
 34 int hash(int k)
 35 {
 36   int i,j,ai,aj,cnt,ret=0,zero=8;
 37   for(i=8;i>0;i--)
 38   {
 39     ai=k/pow10[i]%10;
 40     if(ai==0) zero=8-i;
 41     cnt=0;
 42     for(j=i-1;j>=0;j--)
 43     {
 44       aj=k/pow10[j]%10;
 45       if(aj<ai) cnt++;
 46     }
 47     ret+=cnt*fact[i];
 48   }
 49   z[ret]=zero;
 50   return ret;
 51 }
 52 bool read_case()
 53 {
 54   int i,cnt=0;
 55   char c;
 56   s=0;
 57   while(cnt<9)
 58   {
 59     if(scanf("%c",&c)==EOF)  return false;
 60     if(c>='1' && c<='8' || c=='x')
 61     {
 62       cnt++;
 63       c=(c=='x'?'0':c);
 64       s=s*10+c-'0';
 65     }
 66   }
 67   return true;
 68 }
 69 int move(int k,int pos,int d)
 70 {
 71   int i,j,ni,nj,npos,a;
 72   i=pos/3;
 73   j=pos%3;
 74   ni=i+dx[d];
 75   nj=j+dy[d];
 76   if(ni<0 || nj<0 || ni>=3 || nj>=3) return -1;
 77   npos=ni*3+nj;
 78   a=k/pow10[8-npos]%10;
 79   return k+a*(pow10[8-pos]-pow10[8-npos]);
 80 }
 81 void print(int k)
 82 {
 83   if(p[k]==-1)  return;
 84   print(p[k]);
 85   printf("%c",DIR[dir[k]]);
 86 }
 87 void process()
 88 {
 89   int u,v,uu,vv,d;
 90   node tmp;
 91   memset(vis,0,sizeof(vis));
 92   while(!pq.empty())  pq.pop();
 93   u=s;
 94   uu=hash(u);
 95   p[uu]=-1;
 96   vis[uu]=1;
 97   f[uu]=0;
 98   g[uu]=f[uu]+h(u);
 99   pq.push(make_pair(g[uu],u));
100   while(!pq.empty())
101   {
102     tmp=pq.top(),pq.pop();
103     u=tmp.second;    
104     uu=hash(u);
105     vis[uu]++;
106     if(u==t || u==tp)  break;
107     for(d=0;d<4;d++)
108     {
109       v=move(u,z[uu],d);
110       if(v==-1) continue;
111       vv=hash(v);
112       if(vis[vv]==2)  continue;
113       if(vis[vv]==1 && f[uu]+1<f[vv])
114       {
115         g[vv]+=f[uu]+1-f[vv];
116         f[vv]=f[uu]+1;
117         p[vv]=uu;
118         dir[vv]=d;
119       }
120       else
121       {
122         f[vv]=f[uu]+1;
123         g[vv]=f[vv]+h(v);
124         pq.push(make_pair(g[vv],v));
125         vis[vv]++;
126         p[vv]=uu;
127         dir[vv]=d;
128       }
129     }
130   }
131   if(vis[hash(t)]!=2) puts("unsolvable");
132   else print(hash(t)),printf("\n");
133 }
134 int main()
135 {
136   int i;
137   fact[0]=1;
138   for(i=1;i<9;i++)  fact[i]=fact[i-1]*i;
139   while(read_case())  process();
140   return 0;
141 }