这个题思路简单 但如果实现没有模拟好就容易崩掉 前提：一定一定知道 string 本身就有.find与swap (os:我当时不知道自己转二维数组在转回来一下子就晕了） ok代码思路如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
/* 1 基于什么：基于一个队列 --得到模板
     {  queue初始化（放入起点）
        while(队列不空) do{ 1取出队首 2弹出队首 3自由移动不重复找到所有下一个点放入队列并顺手完成任务 }
     }
   2 如果保证不重复的移动---因为我们的最终目的是找到最短路 所以等于初始化的都是未走的 走过的都改
   3 soon:BFS 1当前状态什么要存 怎么存  2 如何状态转移
   --------------------------------------------------------------------
   ok 讲讲这道题：3*3数字华容道--给予一个初始状态的乱序3*3 1-8有一个空x可以移动问 最少次数能变成1-8x;
   1 我们BFS最重要的是怎么防止重复走
     答：每次走完的状态都存一下次数 如果次数不是0就不行重复了
   2 3*3的矩阵怎么存？
     答：可以把其压缩成一个string 至于存数 可以用 unordered_map来某状态string 时需要移动的步数
   3 各种状态如何变化 
     答：观察题意：变换的根本原因是 x这个空位置 所以遍历其上下左右即可
   4 3*3与string何时用谁
     答：string便于比较找x 用于大全局 3*3仅用于坐标的转移
*/
string endd="12345678x";//终点----切记 不要end 重名
unordered_map<string,int> d;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
queue<string> q;
int bfs(string start)
{  q.push(start);
   d[start]=0;//其实不用写 但还是可以写一下
   /* 思考 如果d【start]=0 走完第一步后又回来了咋办
      答：回来后他这种状态必然比其他状态多走所以不是最优解 
      为了防止过度思考 我们可以 方法1：if(!d[u])gaiwei if（d.count(u)!=0；
   */
   while(q.size())  // d[当前状态]=步数
   {
       auto u=q.front();
       q.pop();
       int distance=d[u];
       if(u==endd)//终点
       {
           return distance;
       }
       int k=u.find('x');
       int x=k/3,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)
           {//先把转为string 才能看是否重复
             swap(u[k],u[a*3+b]);
             if(!d[u])
             {
                 d[u]=distance+1;
                 q.push(u);
             }
             swap(u[k],u[a*3+b]);//若已经走过了 就不看了还原现场
           }
       }
   }
  
   return -1;//如果走不到 
}
signed main()
{   std::ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    string tmp,start;
    for(int i=0;i<9;i++)//很不错放入
    {
        cin>>tmp;
        start+=tmp;
    }
    cout<<bfs(start);
    return 0;
}
/*2. 八数码可解的数学条件
设：
N：数字部分（1-8）的逆序数；
K：空格（x）所在的行号（从下往上数，比如 3*3 矩阵中，空格在第一行则 K=3，第二行 K=2，第三行 K=1）。
可解条件：N + K 的奇偶性 与 目标状态的N+K奇偶性一致。
目标状态（12345678x）：N=0，x 在第三行（从下往上数 K=1）→ 0+1=1（奇数）。
结论：只有初始状态的N+K也是奇数时，才能还原；如果是偶数，必然无解。
*/