B28 A*算法 八数码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
 
struct node{int a[4][4],x,y,pre, kt;char c;};
int kangtuo(node no)
{
    int sum=0;for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)sum=sum*10+no.a[i][j];
    return sum;
}
 
map<int,bool>v;node Q[370000];
char st[4],ss[370000],ys[10];
int tt;
 
int main()
{
    ys[1]='u';ys[2]='d';ys[3]='l';ys[4]='r';
     
    node stno,edno;
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            scanf("%s",st);
            if(st[0]!='x')stno.a[i][j]=st[0]-'0';
            else stno.x=i,stno.y=j,stno.a[i][j]=0;
        }
    }
    stno.kt=kangtuo(stno);
     
    for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)edno.a[i][j]=(i-1)*3+j;
    edno.a[3][3]=0;edno.kt=kangtuo(edno);
     
    v.clear();v[stno.kt]=1;
    bool bk=0;
    int h=1,t=1;
    Q[1]=stno;
    while(h<=t)
    {
        for(int i=0;i<=3;i++)
        {
            node no=Q[h];
            int xx=no.x+dx[i],yy=no.y+dy[i];
             
            if(xx>=1&&xx<=3&&yy>=1&&yy<=3)
            {
                swap(no.a[no.x][no.y],no.a[xx][yy]);
                no.kt=kangtuo(no);
                no.c=ys[i+1];
                no.pre=h;
                no.x=xx;no.y=yy;
                 
                if(v[no.kt]==0)
                {
                    v[no.kt]=1;
                    Q[++t]=no;
                    if(no.kt==edno.kt){bk=1;break;}
                }
            }
        }
        h++;
        if(bk)break;
    }
     
    if(bk)
    {
        tt=0;
        while(t!=1)
        {
            ss[++tt]=Q[t].c;
            t=Q[t].pre;
        }
        for(int i=tt;i>=1;i--)printf("%c",ss[i]);
        printf("\n");
    }
    else printf("unsolvable\n");
    return 0;
}