莫欺少年穷，修魔之旅在这开始—>算法提高课题解

保姆级注释，看不懂你炸我

A*算法

当估价函数为0时，就是 Dijkstra 算法；当权值都为1时，就是 BFS

思路：

1. 此题有个性质：如果逆序对数量是奇数，就永远都无法到达，故可提前判断
2. dist 数组：记录到达该状态的距离
3. pre 数组：记录到达该状态的操作和上一步状态
4. heap 小根堆：记录从起点到终点的估价距离和该状态
5. 估价函数：该状态的各个点和目标状态的曼哈顿距离之和
6. 每次取出队顶元素：从起点到达终点的估价距离最小
7. 注意：取出的元素的状态只有终点才是最小距离
8. 枚举该状态可以到达的新状态，如果该新状态未出现过或比之前到达该状态的距离更小,就更新dist，pre和 heap
9. 最后不要忘了回推路径并且反转

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,string> PIS;
typedef pair<char,string> PCS;

//从该状态到达目标状态的估价函数：各个点与目标状态的曼哈顿距离之和
int f(string state)
{
    int res=0;
    for(int i=0;i<9;i++)
        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)
{
    //枚举四个方向的操作
    char op[5]="urdl";

    //目标字符串
    string end="12345678x";

    //枚举四个方向的方位
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

    //初始化dist数组，更新起点的距离
    unordered_map<string,int> dist;
    dist[start]=0;

    //记录到达此状态的操作和上一步状态
    unordered_map<string,PCS> pre;

    //初始化小根堆，第一元素：从起点到该状态的真实距离+该状态到达目标状态的估价距离；第二元素：该状态
    priority_queue<PIS,vector<PIS>,greater<PIS>> heap;
    heap.push({f(start),start});

    while(heap.size())
    {
        //取出堆顶：从起点到达终点的估价距离最小
        auto t=heap.top();
        heap.pop();

        //取出该状态
        string state=t.y;

        //到达目标字符串
        if(state==end) break;

        //求'x'的坐标
        int x,y;
        for(int i=0;i<9;i++) 
            if(state[i]=='x')
                x=i/3,y=i%3;

        //提前存储该状态，需要反复用到
        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=source;

            //该状态扩展的新状态
            swap(state[x*3+y],state[a*3+b]);

            //该状态之前未出现过或此路径比之前到达该状态的距离更小
            if(!dist.count(state)||dist[source]+1<dist[state])
            {
                //更新扩展出来的新状态的距离
                dist[state]=dist[source]+1;

                //记录到达此状态的操作和上一步状态
                pre[state]={op[i],source};

                //放入队列，记录起点到终点的估价距离和新状态
                heap.push({dist[state]+f(state),state});
            }
        }
    }

    //回推路径
    string res;
    while(end!=start)
    {
        res+=pre[end].x;
        end=pre[end].y;
    }
    reverse(res.begin(),res.end());

    return res;
}

int main()
{
    string start,seq;
    char c;
    while(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&1) cout<<"unsolvable"<<endl;
    else cout<<bfs(start)<<endl;

    return 0;
}