1.八数码

原题链接：https://www.acwing.com/problem/content/description/181/

A*的重点在于利用优先队列记录到达当前节点的真实距离加上从当前节点出发到终点的估计距离，用该信息作为第一关键字来处理各个状态。
在四个方向处理时要注意恢复状态。

#include<iostream>
#include<queue>
#include<cstring>
#include<unordered_map>
#include<algorithm>
using namespace std;

#define x first
#define y second
typedef pair<int,string> PSI;
const int N=10;
string ed="12345678x";

int f(string s)
{
    int res=0;
    for(int i=0;i<9;i++)
    {
        if(s[i]!='x'){
            int a=s[i]-'1';
            if(a!=i){
                res+=abs(a/3-i/3)+abs(a%3-i%3);
            }
        }
    }
    return res;
}

string bfs(string s)
{
    unordered_map<string,int> dist;
    priority_queue<PSI,vector<PSI>,greater<PSI>> heap;
    unordered_map<string,pair<string,char>> pre;
    heap.push({f(s),s});
    char op[4]={'u','d','l','r'};
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    dist[s]=0;
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        string state=t.y;
        if(state==ed){
            break;
        }
        int x1,y1;
        for(int i=0;i<9;i++)
        {
            if(state[i]=='x'){
                x1=i/3,y1=i%3;
            }
        }
        string last=state;
        for(int i=0;i<4;i++)
        {
            int x=x1+dx[i],y=y1+dy[i];
            if(x<0||x>=3||y<0||y>=3) continue;
            swap(state[x*3+y],state[x1*3+y1]);
            if(dist.count(state)==0||dist[last]+1<dist[state]){
                dist[state]=dist[last]+1;
                pre[state]={last,op[i]};
                heap.push({dist[state]+f(state),state});
            }
            swap(state[x*3+y],state[x1*3+y1]);
        }
    }
    string res;
    while(s!=ed){
        res+=pre[ed].y;
        ed=pre[ed].x;
    }
    reverse(res.begin(),res.end());
    return res;
}

int main()
{
    string s;
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        s+=c;
    }
    int cnt=0;
    for(int i=0;i<9;i++)
        for(int j=0;j<i;j++)
        {
            if(s[i]=='x'||s[j]=='x') continue;
            int a=s[i]-'0',b=s[j]-'0';
            if(a<b) cnt++;
        }
    if(cnt&1) puts("unsolvable");
    else{
        cout<<bfs(s)<<endl;
    }
    return 0;
}