广搜+hash+一个小技巧

#include<cstdio>
#include<cstring>
using namespace std;

typedef short state[10]; 

const int maxstate = 1000000;

const int hashmax = 1000003;

state st[maxstate];

state ans;
int tot=0;
int way[10000];

int heada[hashmax], next[maxstate];
int father[hashmax];
int ti[]={0,1,3,-1,-3}; 
int hash(state & s)
{
    int res = 0;
    for(int i = 1;i <= 9;i++)
    res = res * 10 + s[i];
    return res % hashmax;
    
}
int can(int i,int pos)
{
    
    if((pos==3||pos==6||pos==9)&&i==1) return 0;
    if((pos==7||pos==8||pos==9)&&i==2) return 0;
    if((pos==1||pos==4||pos==7)&&i==3) return 0;
    if((pos==1||pos==2||pos==3)&&i==4) return 0;

    return pos+ti[i];
}
int insert(int tail)
{
    int h = hash(st[tail]);
    int u = heada[h];
    while(u!=0) 
    {
        if(memcmp(st[u],st[tail],sizeof(st[tail])) == 0) return 0;
        u=next[u];
    }
    next[tail] = heada[h];
    heada[h] = tail;
    return 1;
} 
void out(int now)
{
    if(now==1)
        return;
    
    way[++tot]=now;

    out(father[now]);

}
int bfs()
{
    int head = 0,tail = 2;
    do
    {
        head++;
         
        int pos;
        
        state & s = st[head];
        if(memcmp(ans,s,sizeof(s)) == 0) 
        {
        out(head);  
        return head;    
        }
        for(int i = 1;i <= 9;i++)
        if(s[i] == 0) pos = i;
         
        
        for(int i=1;i<=4;i++)
        {
            int newpos=can(i,pos); 
    
            if(newpos)
            {
                state & t = st[tail];
                memcpy(&t,&s,sizeof(s));
                t[newpos] = s[pos];
                t[pos] = s[newpos];
                 
        
                father[tail]=head;
                int flag=insert(tail);
                
                if(flag) tail++;
        
                 
            }
            
        }
        
    }while(head<tail);

    return 0;
} 
int main()
{
freopen("in.txt","r",stdin);
    for(int i=1;i<=9;i++) scanf("%d",&st[1][i]);
    for(int i=1;i<=9;i++) scanf("%d",&ans[i]);
    

    int res=bfs();
    

    printf("%d\n",tot);
            for(int i=1;i<=9;i++)
    {
        if(i==4||i==7) printf("\n");
        printf("%d ",st[1][i]);
    } 
    printf("\n\n");
    
    for(int i=tot;i>=1;i--)
    {
        for(int j=1;j<=9;j++)
        {
            if(j==4||j==7) printf("\n");
            printf("%d ",st[way[i]][j]);
        }
        if(i!=1) printf("\n\n");
    }
    
    return 0;
}