A*算法解决八数码

https://blog.csdn.net/lishang6257/article/details/79732420

#include <bits/stdc++.h> 
using namespace std;
#define ll long long 
const int INF = 1e9+7;
const int maxn =1e6+10;
struct Node
{
    int maze[3][3];
    int h,g;
    int x,y;
    int Hash;
    bool operator< (const Node n1) const
    {
        return h!=n1.h? h>n1.h:g>n1.g;
    }
    bool check(){
        if(x>=0&&x<3&&y>=0&&y<3)
            return true ;
        return false;
    }
};
Node s,u,v,tt;
int HASH[9]= {1,1,2,6,24,120,720,5040,40320};
int destination=322560; 
int vis[400000];
int pre[400000];
int way[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
int a[4][4],k;
int get_hash(Node tmp)
{
    int a[9],k=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            a[k++]=tmp.maze[i][j];
    int res=0;
    for(int i=0; i<9; i++)
    {
        int k=0;
        for(int j=0; j<i; j++)
            if(a[j]>a[i]) k++;
        res+=HASH[i]*k;
    }
    return res;
}
bool isok(Node tmp)
{
    int a[9],k=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            a[k++]=tmp.maze[i][j];
    int sum=0;
    for(int i=0; i<9; i++)
        for(int j=i+1; j<9; j++)
            if(a[j]&&a[i]&&a[i]>a[j]) sum++;
    return !(sum&1);
}
int get_h(Node tmp)
{
    int ans=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            if(tmp.maze[i][j])
                ans+=abs(i-(tmp.maze[i][j]-1)/3)+abs(j-(tmp.maze[i][j]-1)%3);
    return ans;
}
void astar()
{
    priority_queue<Node>que;
    que.push(s);
    while(!que.empty())
    {
        u=que.top();
        que.pop();
        for(int i=0; i<4; i++)
        {
            v=u;
            v.x+=way[i][0];
            v.y+=way[i][1];
            if(v.check())
            {
                swap(v.maze[v.x][v.y],v.maze[u.x][u.y]);
                v.Hash=get_hash(v);
                if(vis[v.Hash]==-1&&isok(v))
                {
                    vis[v.Hash]=i;
                    v.g++;
                    pre[v.Hash]=u.Hash;
                    v.h=get_h(v);
                    que.push(v);
                }
                if(v.Hash==destination) return;
            }
        }
    }
}
void print()
{
    string ans;
    ans.clear();
    int cnt = 0 ,nxt=destination;
    while(pre[nxt]!=-1)
    {
        cnt++;
        switch(vis[nxt])
        {
        case 0:
            ans+="Right->";
            break;
        case 1:
            ans+="Left->";
            break;
        case 2:
            ans+="Down->";
            break;
        case 3:
            ans+="Up->";
            break;
        }
        nxt=pre[nxt];
    }
    cout<<"at least you should move "<< cnt <<" steps"<<endl; 
    for(int i=0;i<ans.length()-2;i++)
        cout<<ans[i];
    cout<<endl;
}
int main()
{
    memset(vis,-1,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            scanf("%d",&k);
            if(!k){
                s.maze[i][j] = 0,s.x = i,s.y = j;
            }else{
                s.maze[i][j] = k;
            }
        }
    }
    if(!isok(s)){
        printf("no solution\n");
        return 0;
    }
    s.Hash=get_hash(s);
    if(s.Hash==destination){
        puts("no move");
        return 0;
    }
    vis[s.Hash]=-2;
    s.g=0;
    s.h=get_h(s);
    astar();
    print();
    return 0;
}