思路

思路看起来可能有点乱,不好理解,但是看代码时就会豁然开朗

证明以及细节

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

#define x first
#define y second

using namespace std;

typedef pair<int,string> PIS;

int f(string m)//估计函数
{
    int dt=0;
    for(int i=0;i<9;i++)//这里1~8对应的下标为0~7
    if(m[i]!='x')
    {
        int t=m[i]-'1';//对应下标
        dt=dt+abs(i/3-t/3)+abs(i%3-t%3);//曼哈顿距离
    }
    return dt;//返回总曼哈顿距离
}

string bfs(string start)
{
    string end="12345678x";//终点

    unordered_map<string,int> d;//存储距离
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;//小根堆,将元素的估计终点距离从小到大排序
    unordered_map<string,pair<string,char>> last;//存储一个元素由哪种状态,经过哪种操作得来,跟前面几题一样

    heap.push({f(start),start});//加入起点
    d[start]=0;//起点到起点的距离为0
    //要将操作数组与坐标变化数组一一对应
    char oper[]="udlr";
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

    while(heap.size())
    {
        auto t=heap.top();//队头
        heap.pop();//弹出
        string state=t.y;//记录

        if(t.y==end) break;//终点出列的话就退出

        int x,y;//查找x的横纵坐标
        for(int i=0;i<9;i++)
        if(state[i]=='x')
        {
            x=i/3,y=i%3;
            break;
        }

        string init=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;//越界就跳过
            swap(state[a*3+b],state[x*3+y]);//交换下标位置
            if(!d.count(state)||d[state]>d[init]+1)//如果没有被记录或者小于记录值
            {
                d[state]=d[init]+1;//更新距离
                heap.push({f(state)+d[state],state});//加入堆中
                last[state]={init,oper[i]};//标记由哪种状态转移而来,并且记录执行的操作
            }
            state=init;//因为要扩展到四个方向,所以要还原
        }
    }

    string ans;
    //跟前面几题原来相同
    while(end!=start)
    {
        ans+=last[end].y;
        end=last[end].x;
    }
    reverse(ans.begin(),ans.end());//将其反转
    return ans;
}

int main()
{
    string start,x,c;
    while(cin>>c)//这样输入可以忽视空格
    {
        start+=c;
        if(c!="x") x+=c;
    }

    int res=0;//统计逆序对的数量
    for(int i=0;i<8;i++)
     for(int j=i+1;j<8;j++)
      if(x[i]>x[j]) 
       res++;

    if(res%2) printf("unsolvable\n");//如果逆序对为奇数,就不可能抵达终点
    else cout<<bfs(start)<<endl;//输出答案

    return 0;
}