Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10778 Accepted Submission(s):
2873
Special Judge
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.
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
``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.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<string>
#include<queue>
using namespace std; struct node
{
bool flag;
char str;
int father;
}hash[];
struct st
{
char t[];
};
queue<st>Q;
int ans[]={}; int ktzk(char *c)
{
int i,j,k,sum=;
for(i=;i<=;i++)
{
k=;
for(j=i+;j<=;j++)
if(c[i]>c[j])
k++;
sum=sum+k*ans[-i];
}
return sum;
}
void bfs()
{
int i,k,num,val;
struct st cur,t;
k=ktzk("");
hash[k].flag=true;
hash[k].str='\0';
hash[k].father=k; strcpy(t.t,"");
Q.push(t); while(!Q.empty())
{
cur=Q.front();
Q.pop();
val=ktzk(cur.t);
for(i=;i<=;i++)
{
if(cur.t[i]=='')
{
k=i;
break;
}
}
if(k!= && k!= && k!=)//rigth
{
t=cur;
swap(t.t[k],t.t[k+]);
num=ktzk(t.t);
if(hash[num].flag==false)
{
hash[num].flag=true;
hash[num].str='r';
hash[num].father=val;
Q.push(t);
}
}
if(k!= && k!= && k!=)//left
{
t=cur;
swap(t.t[k],t.t[k-]);
num=ktzk(t.t);
if(hash[num].flag==false)
{
hash[num].flag=true;
hash[num].str='l';
hash[num].father=val;
Q.push(t);
}
}
if(k>=)//u
{
t=cur;
swap(t.t[k],t.t[k-]);
num=ktzk(t.t);
if(hash[num].flag==false)
{
hash[num].flag=true;
hash[num].str='u';
hash[num].father=val;
Q.push(t);
}
}
if(k<=)//D
{
t=cur;
swap(t.t[k],t.t[k+]);
num=ktzk(t.t);
if(hash[num].flag==false)
{
hash[num].flag=true;
hash[num].str='d';
hash[num].father=val;
Q.push(t);
}
}
}
}
void prepare()
{
int i;
for(i=;i<=;i++)
{
hash[i].flag=false;
}
for(i=;i<=;i++) ans[i]=ans[i-]*i;
bfs();
}
int main()
{
prepare();
char a[],b[],c[];
bool tom[];
int i,j,k,cur;
while(gets(a))
{
k=strlen(a);
b[]='\0';
for(i=,j=;i<k;i++)
{
if(a[i]=='x' || (a[i]>=''&&a[i]<=''))
{
if(a[i]=='x')
b[j]='';
else b[j]=a[i];
j++;
}
}
memset(tom,false,sizeof(tom));
for(i=;i<=;i++)
{
tom[b[i]-'']=true;
}
for(i=;i<=;i++)
{
if(tom[i]==false)
break;
}
if(i<=){printf("unsolvable\n");continue;}
cur=ktzk(b);
if(hash[cur].flag==false)
{
printf("unsolvable\n");
continue;
}
k=;
while(hash[cur].father!=cur)
{
c[k]=hash[cur].str;
k++;
cur=hash[cur].father;
}
for(i=;i<=k-;i++)
{
if(c[i]=='u')printf("d");
if(c[i]=='d')printf("u");
if(c[i]=='l')printf("r");
if(c[i]=='r')printf("l");
}
printf("\n");
}
return ;
}