http://acm.hdu.edu.cn/showproblem.php?pid=1043
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
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.
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int qwq[];
char sss[];
int vv[];
bool v[];
int f0;
int counter(string s){
int sum=;
for(int i=;i<=;i++){
qwq[i]=qwq[i-]*i;
}
for(int i=;i<;i++){
int tt=;
for(int j=i+;j<;j++){
if(s[j]<s[i]){
tt++;
}
}
sum+=qwq[-i]*tt;
}
return sum;
}
queue<string>pq;
void bfs(){
while(!pq.empty())pq.pop();
string s0="";
pq.push(s0);
f0=counter(s0);
v[f0]=;
while(!pq.empty()){
string aa=pq.front();pq.pop();
int fs=counter(aa);
//if(fs==76346)cout <<aa<<endl;
for(int i=;i<aa.size();i++){
if(aa[i]==''){
if(i%==){
string bb=aa;
bb[i]=bb[i+];
bb[i+]='';
int f=counter(bb);
if(!v[f]){
v[f]=;
sss[f]='l';
vv[f]=fs;
pq.push(bb);
}
if(i!=){
string cc=aa;
cc[i]=cc[i+];
cc[i+]='';
int f=counter(cc);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='u';
pq.push(cc);
}
}
if(i!=){
string dd=aa;
dd[i]=dd[i-];
dd[i-]='';
int f=counter(dd);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='d';
pq.push(dd);
}
}
}
else if(i%==){
string bb=aa;
bb[i]=bb[i+];
bb[i+]='';
int f=counter(bb);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='l';
pq.push(bb);
}
string cc=aa;
cc[i]=cc[i-];
cc[i-]='';
f=counter(cc);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='r';
pq.push(cc);
}
if(i!=){
string cc=aa;
cc[i]=cc[i+];
cc[i+]='';
int f=counter(cc);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='u';
pq.push(cc);
} }
if(i!=){
string dd=aa;
dd[i]=dd[i-];
dd[i-]='';
int f=counter(dd);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='d';
pq.push(dd);
}
}
}
else{
string bb=aa;
bb[i]=bb[i-];
bb[i-]=''; int f=counter(bb);
// if(fs==76346)
//cout <<f<<" "<<endl;
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='r';
pq.push(bb);
}
if(i!=){
string cc=aa;
cc[i]=cc[i+];
cc[i+]='';
int f=counter(cc); if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='u';
pq.push(cc);
}
}
if(i!=){
string dd=aa;
dd[i]=dd[i-];
dd[i-]='';
int f=counter(dd);
if(!v[f]){
v[f]=;
vv[f]=fs;
sss[f]='d';
pq.push(dd);
}
}
}
}
}
}
}
void init(){
qwq[]=qwq[]=;
for(int i=;i<=;i++){
qwq[i]=qwq[i-]*i;
}
}
int main(){
init();
bfs();
char aa[];
char bb[];
//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],
// aa[6],&aa[7],&aa[8],)){
while(gets(aa)){
if(aa[]=='\0')break;
int tot=;
int len=strlen(aa);
for(int i=;i<len;i++){
if((aa[i]>=''&&aa[i]<='')){
bb[tot++]=aa[i];
}
if(aa[i]=='x'){
bb[tot++]='';
}
}
bb[tot]='\0';
int f=counter(bb);
// cout << f<<" "<<bb<<endl;
//cout <<f<<endl;46103
if(!v[f]){
printf("unsolvable\n");
}
else{
for(int i = f ; i != f0 ; i=vv[i]){
// cout << vv[<<endl;
printf("%c",sss[i]);
//system("pause");
}
printf("\n");
}
}
return ;
}