题解 | #八数码#

题目考点：STL、 bfs
题目大意：可以看成x上下左右移动最终复原八数码。
题目分析：普通的bfs，不过是用map<string, int>储存状态（这里用的unorderedmap，比较快）
（由于用字符串储存，速度会慢很多，建议改用map<int, int>储存，这里就偷懒了）

#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define tb std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
string s1 = "";
queue<string> q;
unordered_map<string, string> d;

ll dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1} }; //方向
char dc[4] = {'u', 'r', 'd', 'l'};                  //方向代号


string bfs(string s){

    q.push(s); //初始状态
    d[s] = "";
    string ends = "12345678x";  //结束状态

    while(q.size()){
        auto t = q.front(); q.pop();
        if(t == ends)return d[t];       //恢复完毕，返回

        ll pos = t.find('x');           //找到当前字符串中x的位置
        ll x = pos / 3, y = pos % 3;    //一维位置转二维坐标
        string dt = d[t];               //当前字符串

        for(ll i = 0; i < 4; i++){
            ll a = x + dir[i][0], b = y + dir[i][1];
            if(a >= 0 && a < 3 && b >= 0 && b < 3){
                swap(t[a*3+b], t[pos]); //拓展方向
                if(!d.count(t)){
                    d[t] = dt + dc[i]; //当前字符串加上拓展方向的代号
                    //cout<<t<<' '<<d[t]<<'\n'; //debug状态
                    q.push(t);
                }
                swap(t[a*3+b], t[pos]); //拓展一次后恢复，继续循环下一个状态
            }
        }
    }
    return "unsolvable";     //未找到，返回无解
}

int main()
{
    char aa[2];
    for(ll i = 1; i <= 9; i++){
        cin>>aa;   //读取字符方式，避免%c读数发生错误（不管什么时候，尽量避免%c）
        s1 += *aa;
    }
    cout<<bfs(s1);
    return 0;
}