https://www.acwing.com/problem/content/847/
本质还是bfs。状态通过字符串(一维保存方法),在转移时通过计算变成二维状态
标记数组通过unorder_map实现

#include <iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ans=-1;
int bfs(string start){
    string end="12345678x";
    queue<string>q;
    unordered_map<string,int>dist;
    q.push(start);
    dist[start]=0;
    while(q.size()){
        auto t=q.front();
        q.pop();
        int temp=dist[t];
        if(t==end){
            return ans=temp;
        }
        int k=t.find('x');//找到x的一维坐标
        int x=k/3;//将一维坐标转化成二维坐标
        int y=k%3;
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0 && a<3 && b>=0 &&b<3){
                int nk=a*3+b;//二维坐标转化成一维坐标
                swap(t[k],t[nk]);
                if(!dist.count(t)){
                    dist[t]=temp+1;
                    q.push(t);
                }
                swap(t[k],t[nk]);
            }
        }
    }

}
int main(){
    string start;
    for(int i=0;i<9;i++){
        char c;
        cin>>c;
        start+=c;
    }
    bfs(start);
    cout<<ans;
  return 0;
}
//  freopen("testdata.in", "r", stdin);