Eight

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30907 Accepted Submission(s): 8122
Special Judge

Problem Description

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:


 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:


 1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8
 9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12
13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x
            r->            d->            r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.

Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

1 2 3
x 4 6
7 5 8
is described by this list:

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

Sample Input

2 3 4 1 5 x 7 6 8

Sample Output

ullddrurdllurdruldr

题解：裸的康拓展开

使用康拓展开对全排列进行hash，然后使用bfs从末状态开始跑，跑到的状态都是有解的状态，否则输入的初状态无解，在bfs过程记录这一步的下一步即可。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 int qwq[10];
  7 char sss[403200];
  8 int vv[403200];
  9 bool v[403200];
 10 int f0;
 11 int counter(string s){
 12     int sum=0;
 13     for(int i=2;i<=8;i++){
 14         qwq[i]=qwq[i-1]*i;
 15     }
 16     for(int i=0;i<9;i++){
 17         int tt=0;
 18         for(int j=i+1;j<9;j++){
 19             if(s[j]<s[i]){
 20                 tt++;
 21             }
 22         }
 23         sum+=qwq[8-i]*tt;
 24     }
 25     return sum;
 26 }
 27 queue<string>pq;
 28 void bfs(){
 29     while(!pq.empty())pq.pop();
 30     string s0="123456789";
 31     pq.push(s0);
 32     f0=counter(s0);
 33     v[f0]=1;
 34     while(!pq.empty()){
 35         string aa=pq.front();pq.pop();
 36         int fs=counter(aa);
 37        //if(fs==76346)cout <<aa<<endl;
 38         for(int i=0;i<aa.size();i++){
 39             if(aa[i]=='9'){
 40                 if(i%3==0){
 41                     string bb=aa;
 42                     bb[i]=bb[i+1];
 43                     bb[i+1]='9';
 44                     int f=counter(bb);
 45                     if(!v[f]){
 46                         v[f]=1;
 47                         sss[f]='l';
 48                         vv[f]=fs;
 49                         pq.push(bb);
 50                     }
 51                     if(i!=6){
 52                         string cc=aa;
 53                         cc[i]=cc[i+3];
 54                         cc[i+3]='9';
 55                         int f=counter(cc);
 56                         if(!v[f]){
 57                             v[f]=1;
 58                             vv[f]=fs;
 59                             sss[f]='u';
 60                             pq.push(cc);
 61                         }
 62                     }
 63                     if(i!=0){
 64                         string dd=aa;
 65                         dd[i]=dd[i-3];
 66                         dd[i-3]='9';
 67                         int f=counter(dd);
 68                         if(!v[f]){
 69                             v[f]=1;
 70                             vv[f]=fs;
 71                             sss[f]='d';
 72                             pq.push(dd);
 73                         }
 74                     }
 75                 }
 76                 else if(i%3==1){
 77                      string bb=aa;
 78                     bb[i]=bb[i+1];
 79                     bb[i+1]='9';
 80                     int f=counter(bb);
 81                     if(!v[f]){
 82                         v[f]=1;
 83                         vv[f]=fs;
 84                         sss[f]='l';
 85                         pq.push(bb);
 86                     }
 87                      string cc=aa;
 88                     cc[i]=cc[i-1];
 89                     cc[i-1]='9';
 90                     f=counter(cc);
 91                     if(!v[f]){
 92                         v[f]=1;
 93                         vv[f]=fs;
 94                         sss[f]='r';
 95                         pq.push(cc);
 96                     }
 97                     if(i!=7){
 98                          string cc=aa;
 99                         cc[i]=cc[i+3];
100                         cc[i+3]='9';
101                         int f=counter(cc);
102                         if(!v[f]){
103                             v[f]=1;
104                             vv[f]=fs;
105                             sss[f]='u';
106                             pq.push(cc);
107                         }
108 
109                     }
110                     if(i!=1){
111                         string dd=aa;
112                         dd[i]=dd[i-3];
113                         dd[i-3]='9';
114                         int f=counter(dd);
115                         if(!v[f]){
116                             v[f]=1;
117                             vv[f]=fs;
118                             sss[f]='d';
119                             pq.push(dd);
120                         }
121                     }
122                 }
123                 else{
124                      string bb=aa;
125                     bb[i]=bb[i-1];
126                     bb[i-1]='9';
127 
128                     int f=counter(bb);
129                    // if(fs==76346)
130                    //cout <<f<<"  "<<endl;
131                     if(!v[f]){
132                         v[f]=1;
133                         vv[f]=fs;
134                         sss[f]='r';
135                         pq.push(bb);
136                     }
137                     if(i!=8){
138                         string cc=aa;
139                         cc[i]=cc[i+3];
140                         cc[i+3]='9';
141                         int f=counter(cc);
142 
143                         if(!v[f]){
144                             v[f]=1;
145                             vv[f]=fs;
146                             sss[f]='u';
147                             pq.push(cc);
148                         }
149                     }
150                     if(i!=2){
151                         string dd=aa;
152                         dd[i]=dd[i-3];
153                         dd[i-3]='9';
154                         int f=counter(dd);
155                         if(!v[f]){
156                             v[f]=1;
157                             vv[f]=fs;
158                             sss[f]='d';
159                             pq.push(dd);
160                         }
161                     }
162                 }
163             }
164         }
165     }
166 }
167 void init(){
168     qwq[0]=qwq[1]=1;
169     for(int i=2;i<=8;i++){
170         qwq[i]=qwq[i-1]*i;
171     }
172 }
173 int main(){
174     init();
175     bfs();
176     char aa[100];
177     char bb[100];
178     //while(scanf("%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c",aa[0],aa[1],aa[2],aa[3],aa[4],aa[5],
179      //           aa[6],&aa[7],&aa[8],)){
180     while(gets(aa)){
181         if(aa[0]=='')break;
182         int tot=0;
183         int len=strlen(aa);
184         for(int i=0;i<len;i++){
185             if((aa[i]>='0'&&aa[i]<='8')){
186                 bb[tot++]=aa[i];
187             }
188             if(aa[i]=='x'){
189                 bb[tot++]='9';
190             }
191         }
192         bb[tot]='';
193         int f=counter(bb);
194        // cout << f<<"   "<<bb<<endl;
195         //cout <<f<<endl;46103
196         if(!v[f]){
197             printf("unsolvable
");
198         }
199         else{
200             for(int i = f ; i != f0 ; i=vv[i]){
201                // cout << vv[<<endl;
202              printf("%c",sss[i]);
203                 //system("pause");
204             }
205             printf("
");
206         }
207     }
208     return 0;
209 }

View Code