题目：八数码
:https://www.acwing.com/problem/content/847/

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

using namespace std;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs(string s){
    unordered_map<string, int>mp;
    queue<string>q;
    string end = "12345678x";   //记录结束状态
    mp[s] = 0;  
    q.push(s);
    while(q.size()){
        auto t = q.front();
        q.pop();
        int distance = mp[t];   //记录改变到当前状态t所需步长
        if(t == end)    return distance;    //如果找到结束状态则输出步长
        int pos = t.find('x');  //找到x的位置
        int x = pos / 3, y = pos % 3;   //从1维找到2维中x的位置
        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){ 
                swap(t[a * 3 + b], t[pos]); //更新新的x的位置
                if(!mp.count(t)){   //如果该t状态没有出现过，则压入队列中
                    q.push(t);
                    mp[t] = distance + 1;   //到该t状态的步长+1
                }
                swap(t[a * 3 + b], t[pos]); //恢复现场
            }
        }
    }
    return -1;
}

int main(){
    string s;
    for(int i = 0; i < 9; i ++ ){
        char c;
        cin>>c;
        s += c;
    }
    cout<<bfs(s);
    return 0;
}

题目2：八数码的路径记录
：https://vjudge.net/problem/HDU-1043

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

using namespace std;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char change[] = {'d', 'l', 'u', 'r'};   //方向相反 
unordered_map<string,string>mp;
queue<string>q;

void bfs(){
    string s = "12345678x"; 
    q.push(s);
    while(q.size()){
        string t = q.front();
        q.pop();
        int pos = t.find('x');
        int x = pos / 3, y = pos % 3;
        string dis = mp[t];
        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){ 
                swap(t[a * 3 + b], t[pos]);
                if(!mp.count(t)){
                    mp[t] = change[i] + dis;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[pos]); //恢复现场
            }
        }
    }
}

int main(){
    bfs();
    char c;
    while(cin>>c){
        string s = "";
        s += c;
        for(int i = 2; i <= 9; i ++ ){
            cin>>c;
            s += c;
        }
        if(!mp.count(s))    cout<<"unsolvable\n";
        else{
            string ans = mp[s];
            cout<<ans.c_str()<<'\n';
        }
    } 
    return 0;
}