$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. 设定初始字符串和目标字符串
2. 枚举每一个状态可以达到的状态
3. 第一次枚举到的目标字符串就是最小步数
4. 如何转移状态：交换坐标即可，等操作完后需要返回原状态

完整代码

#include<bits/stdc++.h>

using namespace std;

int bfs(string start)
{
    //目标字符串
    string end="12345678x";

    //初始化队列q
    queue<string> q;
    q.push(start);

    //表示初始状态到该状态的最小步数
    unordered_map<string,int> d;

    //枚举四个方向
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        //提前存储，后面求距离需要用到
        int distance=d[t];
        if(t==end) return d[t];

        //取该点坐标
        int k=t.find('x');
        int x=k/3,y=k%3;

        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) continue;

            swap(t[k],t[a*3+b]);

            //没走过该状态
            if(!d.count(t))
            {
                d[t]=distance+1;
                q.push(t);
            }

            //返回原状态，继续枚举下一个状态
            swap(t[k],t[a*3+b]);
        }
    }

    return -1;
}

int main()
{
    string start;
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        start+=c;
    }

    cout<<bfs(start)<<endl;

    return 0;
}