学步园

POJ_1077

经典的八数码问题，做完之后突然想到一句台词：“我的人生又趋于完整了一点……”。

一开始接触这个确实觉得比较难，后来突然在刘汝佳书上发现原来是有讲这个问题的，于是我如获至宝，赶紧研究起刘汝佳的代码来，边学边写，总算是把代码写完了，同时又在他的代码和提示的基础上自己写了打印路径的方式。

研究这个题的代码时，第一次比较认真地看了Hash的有关内容，掌握了一些基础的Hash判重的方法，同时对状态的表示也有了更深一步的理解，总之收获不菲呀。

#include<stdio.h>
#include<string.h>
#define MAX 1000000
#define HASH 1000003
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int dis[MAX],goal[9],st[MAX][9],fa[MAX],move[MAX];
int head[HASH],next[MAX];
char path[500000];
void lookup()
{
    memset(head,0,sizeof(head));    
}
int hash(int s)
{
int v=0,i;
for(i=0;i<9;i++)
        v=v*10+st[s][i];
return v%HASH;
}
int insert(int s)
{
int h,u;
    h=hash(s);
for(u=head[h];u!=0;u=next[u])
if(memcmp(st[u],st[s],sizeof(st[s]))==0)
return 0;
    next[s]=head[h];
    head[h]=s;
return 1;
}
int bfs()
{
int x,y,z,d,newx,newy,newz,front,rear;
    lookup();
    front=1;
    rear=2;
    dis[1]=fa[1]=0;
while(front<rear)
    {
if(memcmp(st[front],goal,sizeof(goal))==0)
return front;
for(z=0;z<9;z++)
if(st[front][z]==0)
break;
        x=z/3;
        y=z%3;
for(d=0;d<4;d++)
        {
            newx=x+dx[d];
            newy=y+dy[d];
            newz=newx*3+newy;
if(newx>=0&&newx<3&&newy>=0&&newy<3)
            {
                memcpy(st[rear],st[front],sizeof(st[front]));
                st[rear][newz]=st[front][z];
                st[rear][z]=st[front][newz];
if(insert(rear))
                {
                    dis[rear]=dis[front]+1;
                    move[rear]=d;
                    fa[rear]=front;
                    rear++;
                }
            }
        }
        front++;
    }
return 0;
}
int main()
{
int i,j,ans;
char b[5];
for(i=0;i<9;i++)
    {
        scanf("%s",b);
if(b[0]=='x')
            st[1][i]=0;
else
            st[1][i]=b[0]-'0';    
    }
for(i=0;i<9;i++)
        goal[i]=(i+1)%9;
    ans=bfs();
if(ans==0)
        printf("unsolvable\n");
else
    {
        i=dis[ans];
        path[i]='\0';
        j=ans;
for(i-=1;j!=0;i--,j=fa[j])
switch(move[j])
            {
case 0: path[i]='u';break;
case 1: path[i]='d';break;
case 2: path[i]='l';break;
case 3: path[i]='r';break;
            }
        printf("%s\n",path);
    }
return 0;
}