Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11226 Accepted Submission(s): 3013
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 <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef struct eight
{
char a[][];
int statu,nowx,nowy;
} eight;
eight s,e;
int f[],flag[],ok;
int father1[],father2[];
int move1[],move2[],last;
queue<eight>q1,q2;
void init()
{
f[]=;
int i;
for(i=; i<; i++)f[i]=f[i-]*i;
}
void work(eight &a)
{
int i,j,k=,ans=,t;
char b[];
for(i=; i<; i++)
{
for(j=; j<; j++)
{
if(a.a[i][j]=='x')a.nowx=i,a.nowy=j;
b[k++]=a.a[i][j];
}
}
k=;
for(i=; i<; i++)
{
t=;
for(j=i+; j<; j++)
if(b[j]<b[i])t++;
ans+=f[k--]*t;
}
a.statu=ans;
}
void copy(eight &a,eight &b)
{
int i,j;
for(i=; i<; i++)
for(j=; j<; j++)a.a[i][j]=b.a[i][j];
}
int w[][]= {{,},{,-},{,},{-,}};
void ex_BFS(eight &now,int n,int check)
{
int i,r,c;
eight in;
for(i=; i<; i++)
{ r=now.nowx+w[i][];
c=now.nowy+w[i][];
if(r>=&&r<&&c>=&&c<)
{
copy(in,now);
swap(in.a[r][c],in.a[now.nowx][now.nowy]);
work(in);
if(flag[in.statu]!=n)
{
if(n==)
{
q1.push(in);
father1[in.statu]=now.statu;
move1[in.statu]=i;
}
else
{
q2.push(in);
father2[in.statu]=now.statu;
move2[in.statu]=i;
}
if(flag[in.statu]==check)
{
ok=;
last=in.statu;
return ;
}
flag[in.statu]=n;
}
}
}
}
bool TBFS(eight &s,eight &e)
{
memset(flag,,sizeof(flag));
memset(move1,-,sizeof(move1));
memset(move2,-,sizeof(move2));
memset(father1,-,sizeof(father1));
memset(father2,-,sizeof(father2));
eight now;
ok=;
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
q1.push(s),flag[s.statu]=;
q2.push(e),flag[e.statu]=;
while((!q1.empty())||(!q2.empty()))
{
now=q1.front();
q1.pop();
ex_BFS(now,,);
if(ok)return ; now=q2.front();
q2.pop();
ex_BFS(now,,);
if(ok)return ;
}
return ;
}
bool check1(eight &s)
{
int i,j,k=;
char b[];
for(i=; i<; i++)
for(j=; j<; j++)
b[k++]=s.a[i][j];
int ans=;
for(i=; i<; i++)
{
if(b[i]!='x')
for(j=; j<i; j++)
if(b[j]!='x'&&b[i]<b[j])ans++;
}
return (ans&);
}
void printpath()
{
deque<char>q;
while(!q.empty())q.pop_back();
int now=last;
while(father1[now]!=-)
{
if(move1[now]==)q.push_back('r');
else if(move1[now]==)q.push_back('l');
else if(move1[now]==)q.push_back('d');
else if(move1[now]==)q.push_back('u');
now=father1[now];
}
while(!q.empty())
{
cout<<q.back();
q.pop_back();
} now=last;
while(father2[now]!=-)
{
if(move2[now]==)cout<<'l';
else if(move2[now]==)cout<<'r';
else if(move2[now]==)cout<<'u';
else if(move2[now]==)cout<<'d';
now=father2[now];
}
}
int main()
{
int i,j;
init();
char w;
while(cin>>w)
{
char an='';
for(i=; i<; i++)
for(j=; j<; j++)
{
if(i||j)
cin>>s.a[i][j];
e.a[i][j]=an++;
}
s.a[][]=w; e.a[][]='x';
if(check1(s))
{
cout<<"unsolvable"<<endl;
continue;
}
work(s);
work(e);
if(s.statu==e.statu)
{
cout<<endl;
continue;
}
if(TBFS(s,e))
{
printpath();
cout<<endl;
}
else
cout<<"unsolvable"<<endl;
} }