题解 | #八数码#

关于看了他人提交后发现内存和时间比我远小一个数量级，不服输的我花了几个小时终于优化成功！！！

1. 将string进行hash可以极大提升速度和降低开销；
2. 为了方便转换，我将题中的'x'替换为'0'（本题刚好用不到0这个数字，可以用来替代！），可以方便相互转换；
3. 注意数字转回字符串时，'0'开头的字符串转为数字后记得转回时在第一个位置添加'0'啊，这是由于第2步造成的；
4. 看了别人的代码，发现有用优先队列的，突然发现这个题还有个trick，就是最终找12345678x(0)实际上是可组成的数字里较小的了，可以选队列中数字较小的优先去操作，大概率能先搜索到答案！！
5. 使用优先队列一定要小心，不要学我debug了半天。在向四个方向延伸的时候，可以入队的一定不要直接入，用一个tempq临时存起来！！！因为一旦入队了，你pop的就不是第一个了。。。（当然，也可以选择取到top的信息后直接pop即可，效果更好，可以自行改下代码）。

555，还是得多做才知道错在哪里。

#include<algorithm>
#include<cstring>
#include<bitset>
#include<limits.h>
#include<vector>
#include<iomanip>
#include<cmath>
#include<stack>
#include<map>
#include<deque>
#include<queue>
#include<set>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
using namespace std;

constexpr int ms[4][2] = { 0,-1,0,1,-1,0,1,0 };
constexpr char chms[4] = { 'l','r','u','d' };
string init;
unordered_set<int>his;
constexpr int ans = 123456780;

priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>>q;
// queue<pair<int,string>>q;

int main(int argc, char const* argv[])
{
    char ch;
    for (int i = 0; i < 9; i++)
    {
        cin >> ch;
        init.push_back(ch);
        if (init[i] == 'x')init[i] = '0';
    }
    int tempx, tempy, nx, ny, pos, num = stoi(init), newnum;
    q.emplace(make_pair(num, ""));
    his.emplace(num);

    string temp, temppath;
    string ret = "unsolvable";
    string numstring;
    queue<pair<int, string>>tempq;
    while (!q.empty())
    {
        num = q.top().first;
        if (num == ans) {
            ret = q.top().second;
            break;
        }
        numstring = to_string(num);
        if (numstring.size() == 8)numstring.insert(numstring.begin(), '0');
        pos = numstring.find('0');
        tempx = pos / 3, tempy = pos % 3;
        for (int i = 0; i < 4; i++)
        {
            nx = tempx + ms[i][0], ny = tempy + ms[i][1];
            if (nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2) {
                temppath = q.top().second + chms[i], temp = numstring;
                swap(temp[nx * 3 + ny], temp[tempx * 3 + tempy]);
                newnum = stoi(temp);
                if (!his.count(newnum)) {
                    tempq.emplace(make_pair(newnum, temppath));
                    his.emplace(newnum);
                }
            }
        }
        q.pop();
        while (!tempq.empty())
        {
            q.emplace(tempq.front());
            tempq.pop();
        }
    }
    cout << ret << endl;
    return 0;
}