用c++实现A*算法的九宫重排

下面是用C++实现A*算法的九宫重排的代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>

#define MAXN 3
#define MAXS 500000
#define MAXH 999983

using namespace std;

const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};

struct node
{
    int map[MAXN][MAXN];
    int hx;
    int x,y;
    int g,f;
    int pre;
}start,goal,temp;

int cnt,head[MAXH],next[MAXS],state[MAXS];
node e[MAXS];
int ans[MAXS];

void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}

int get_hash(node u)
{
    int k=0;
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
            k=k*10+u.map[i][j];
    return k%MAXH;
}

int find(node u)
{
    int h=get_hash(u);
    for(int i=head[h];i!=-1;i=next[i])
        if(memcmp(e[i].map,u.map,sizeof(u.map))==0)
            return i;
    return -1;
}

void insert(node u)
{
    int h=get_hash(u);
    e[cnt]=u;
    state[cnt]=u.hx;
    next[cnt]=head[h];
    head[h]=cnt++;
}

int h(node u)
{
    int ans=0;
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
        {
            int x=(u.map[i][j]-1)/MAXN;
            int y=(u.map[i][j]-1)%MAXN;
            ans+=abs(x-i)+abs(y-j);
        }
    return ans;
}

void A_star()
{
    priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > > q;
    memset(ans,-1,sizeof(ans));
    start.g=0;
    start.f=h(start);
    start.hx=get_hash(start);
    insert(start);
    q.push(make_pair(start.f,0));
    while(!q.empty())
    {
        int f=q.top().first;
        int u=q.top().second;
        q.pop();
        if(ans[state[u]]!=-1)
            continue;
        ans[state[u]]=e[u].g;
        for(int i=0;i<4;i++)
        {
            int nx=e[u].x+dx[i];
            int ny=e[u].y+dy[i];
            if(nx<0||nx>=MAXN||ny<0||ny>=MAXN)
                continue;
            temp=e[u];
            temp.g=e[u].g+1;
            temp.f=temp.g+h(temp);
            swap(temp.map[e[u].x][e[u].y],temp.map[nx][ny]);
            temp.x=nx;
            temp.y=ny;
            temp.pre=u;
            int v=find(temp);
            if(v==-1)
            {
                temp.hx=get_hash(temp);
                insert(temp);
                q.push(make_pair(temp.f,cnt-1));
            }
            else if(ans[state[v]]==-1||ans[state[v]]>temp.g)
            {
                e[v]=temp;
                ans[state[v]]=temp.g;
                q.push(make_pair(temp.f,v));
            }
        }
    }
}

int main()
{
    init();
    int x;
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
        {
            scanf("%d",&x);
            start.map[i][j]=x;
            if(x==0)
            {
                start.x=i;
                start.y=j;
            }
        }
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
        {
            scanf("%d",&x);
            goal.map[i][j]=x;
            if(x==0)
            {
                goal.x=i;
                goal.y=j;
            }
        }
    A_star();
    int t=find(goal);
    printf("%d\n",ans[state[t]]);
    return 0;
}

这里的A*算法是用了一个优先队列来存储结点，每次取出f值最小的结点进行扩展。在扩展一个结点时，我们首先计算出它的估价函数值h，然后计算出g值和f值，根据f值把结点插入到优先队列中，同时在插入时记录下当前状态的哈希值，以便后面进行查找。我们还需要记录下每个状态到达目标状态的步数，这里使用了一个ans数组来记录。在查找的过程中，如果发现当前状态已经被访问过，并且到达目标状态的步数比之前更小，我们就更新这个状态。最后，当我们找到目标状态时，输出到达目标状态的步数即可。