估价函数：

当前状态每个数与它目标位置的曼哈顿距离之和

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

char a[15];

typedef pair<int,string> pii;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char op[]={'d','r','u','l'};

int f(string state)
{
    //找的这个估计距离，一定满足<=真实距离
    int res=0;
    for(int i=0;i<state.size();i++)
    {
        //比如t=3，i=0，意思就是3本来该在的位置是t/3，可是他却在i/3，计算一下这个距离，y坐标同理
        if(state[i]!='x')
        {
            int t=state[i]-'1';
            res+=abs(i/3-t/3)+abs(i%3-t%3);
        }
    }
    return res;
}

string bfs(string start)
{
    string end="12345678x";
    unordered_map<string, int> dist;
    priority_queue<pii , vector<pii> , greater<pii>> heap;
    //记录是从哪个状态转移过来的，且操作是什么
    unordered_map<string,pair<char,string>> prev;

    dist[start]=0;
    heap.push({f(start) , start});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        string state=t.second;
        if(state==end) break;

        int x,y;
        for(int i=0;i<9;i++)
        {
            if(state[i]=='x')
            {
                x=i/3,y=i%3;
                break;
            }
        }
        string source=state;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>=3||b<0||b>=3) continue;
            //在每次交换之前，把state恢复原状(恢复现场)
            state=source;
            swap(state[x*3+y],state[a*3+b]);
            //若这个状态之前没有被拓展过,或拓展过的距离大于当前距离+1
            if(dist.count(state)==0||dist[state]>dist[source]+1)
            {
                dist[state]=dist[source]+1;
                prev[state]={op[i],source};
                heap.push({dist[state]+f(state),state});
            }
        }
    }
    string res;
    while(end!=start)
    {
        res+=prev[end].first;
        end=prev[end].second;
    }
    reverse(res.begin(),res.end());
    return res;
}



int main()
{

    string start , seq;
    for(int i = 0 ; i < 9 ; i++)
    {
        char c;
        cin >> c;
        start += c;
        if(c != 'x') seq += c;
    }

    int cnt = 0;
    for(int i = 0 ; i < 8 ; i ++)
        for(int j = i + 1 ; j < 8 ; j++)
            if(seq[i] > seq[j])
                cnt++;

    if(cnt % 2) puts("unsolvable");
    else cout << bfs(start) << endl;

    return 0;

}