原题链接

题解1：朴素广搜

注意细节

code1

#include<bits/stdc++.h>
using namespace std;
int poi[4]={-3,1,-1,3};
int main()
{
    string s;
    cin>>s;
    queue<string> q;
    map<string,int> rec;
    q.push(s);
    rec[s]=1;
    while(q.size())
    {
        string now=q.front();
        q.pop();
        if(now=="123804765")break;
        for(int i=0;i<9;i++)
        if(now[i]=='0')
        {
            for(int j=0;j<4;j++)
            {
                int id=i+poi[j];
                if(id<0||id>8||id==2&&i==3||id==3&&i==2||id==5&&i==6||id==6&&i==5)continue;//注意细节，如果位于矩阵边缘就不能进行某些操作！！
                string next=now;
                swap(next[i],next[id]);
                if((rec[next]>rec[now]+1||!rec[next])&&(rec[next]=rec[now]+1)) q.push(next);
            }
            break;
        }
    }


    cout<<rec["123804765"]-1;
    return 0;
}