样例

最少—>BFS
解题思路：
考虑 queue<???>q
将棋盘作为队列元素，使用map代替数组存储距离
其他与常规BFS类似

map使用方法
map<string,int>q;
string–数组的下标 int–数组存储的类型
string:key int:value类型
使用方法：类似于数组，例如：
q[“abc”]=1;
通用函数：
q.size();
q.count(“abc”); //如果存在key为abc，则返回1，否则返回0

题目中使用unordered_map，可以节省时间，避免超时。
一些变量定义的地方要搞清楚是在循环内还是在循环外
注意获取和处理数据输入的方法

C++ 代码

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

using namespace std;

string mp="";
unordered_map<string,int> d;
queue<string>q;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int bfs(){
    q.push(mp);
    d[mp]=0;

    while(!q.empty()){
        string t=q.front();
        q.pop();
        int index=t.find('x');
        for(int i=0;i<4;i++){
            int ix=index/3;
            int iy=index%3;
            ix+=dx[i];
            iy+=dy[i];
            int dindex=ix*3+iy;
            char temp=t[dindex];
            mp=t;
            mp[dindex]='x';
            mp[index]=temp;
            //swap(mp[dindex],mp[index]);

            if(ix<0||iy<0||ix>2||iy>2||d.count(mp)!=0) continue;

            q.push(mp);
            d[mp]=d[t]+1;
            if(mp=="12345678x") return d[mp];
        }

    }
    return -1;




}


int main(){
    char ch;
    for(int i=0;i<9;i++){
        cin>>ch;
        mp+=ch;
    }
    cout<<bfs();


    return 0;
}