20091006
比较经典的一个题目，下面是原题和我的代码。
1077 Eight
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 6197 | Accepted: 2670 | Special Judge | ||
Description
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
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
a solution. The string should include no spaces and start at the beginning of the line.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
Source
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct node
{
char sta[3][3];
char posr,posc;
char ope;
int lev;
int dis;
struct node *next;
}NODE;
int Hash(NODE *cur)
{
static int i,j,sum,pro,rev;
sum=0;
for(pro=i=1;i<9;i++)
{
pro*=i;
for(rev=j=0;j<i;j++)
if(cur->sta[0][j]>cur->sta[0][i])
rev++;
sum+=pro*rev;
}
return sum;
}
void Change(NODE *cur,char ope)
{
char t;
t=cur->sta[cur->posr][cur->posc];
switch(ope)
{
case 'u':
cur->sta[cur->posr][cur->posc]=cur->sta[cur->posr+1][cur->posc];
cur->posr++;
break;
case 'd':
cur->sta[cur->posr][cur->posc]=cur->sta[cur->posr-1][cur->posc];
cur->posr--;
break;
case 'l':
cur->sta[cur->posr][cur->posc]=cur->sta[cur->posr][cur->posc+1];
cur->posc++;
break;
case 'r':
cur->sta[cur->posr][cur->posc]=cur->sta[cur->posr][cur->posc-1];
cur->posc--;
break;
}
cur->sta[cur->posr][cur->posc]=t;
}
void PrintPre(NODE *cur,char table[])
{
char t;
if((t=table[Hash(cur)])!='\b')
{
Change(cur,t);
PrintPre(cur,table);
putchar(t);
}
}
void End(NODE *cur,char table[])
{
Change(cur,cur->ope);
PrintPre(cur,table);
putchar(cur->ope);
}
int GetPar(NODE *cur)
{
int i,j,sum=0;
for(i=1;i<9;i++)
for(j=0;j<i;j++)
if((*cur->sta)[j]!='9'&&(*cur->sta)[j]>(*cur->sta)[i])
sum++;
return sum%2;
}
void BrushDis(NODE *cur)
{
static int sum,i,j,t;
for(sum=i=0;i<3;i++)
for(j=0;j<3;j++)
{
t=cur->sta[i][j]-'0'-1;
sum+=abs(t/3-i)+abs(t%3-j);
}
cur->dis=sum;
}
void Insert(NODE *cur,NODE *head)
{
cur->next=head->next;
head->next=cur;
}
int main(void)
{
int i,j,min,r,c;
char table[362880]={0},temp[20],dir[4][3]={1,0,'d',-1,0,'u',0,1,'r',0,-1,'l'};
NODE *head,*cur,*t,*pre;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
cur=(NODE *)malloc(sizeof(NODE));
cur->ope='\b';
cur->lev=0;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
scanf("%s",temp);
if('x'==*temp)
{
cur->posr=i;
cur->posc=j;
cur->sta[i][j]='9';
}
else
cur->sta[i][j]=*temp;
}
if(GetPar(cur))
{
printf("unsolvable");
return 0;
}
BrushDis(cur);
Insert(cur,head);
while(1)
{
for(min=((unsigned int)(~0))>>1,pre=head,cur=head->next;cur!=NULL;pre=cur,cur=cur->next)
if(cur->dis+cur->lev<min)
{
min=cur->dis+cur->lev;
t=pre;
}
cur=t->next;
t->next=cur->next;
if(0==cur->dis)
{
End(cur,table);
free(cur);
while(head!=NULL)
{
pre=head;
head=head->next;
free(pre);
}
return 0;
}
for(i=0;i<4;i++)
{
r=cur->posr+dir[i][0];
c=cur->posc+dir[i][1];
if(r>=0&&r<3&&c>=0&&c<3)
{
t=(NODE *)malloc(sizeof(NODE));
for(j=0;j<9;j++)
*(*t->sta+j)=*(*cur->sta+j);
t->sta
[c]='9';
t->sta[cur->posr][cur->posc]=cur->sta
[c];
if(table[Hash(t)])
{
free(t);
continue;
}
t->ope=dir[i][2];
t->posr=r;
t->posc=c;
t->lev=cur->lev+1;
BrushDis(t); //也可用cur->dis计算
Insert(t,head);
}
}
table[Hash(cur)]=cur->ope;
free(cur);
}
}