广搜

#include<bits/stdc++.h>
using namespace std;
string s;
map<string ,int >vis;
int dx[4]={-3,3,1,-1};
void bfs(){
    queue<string >que;
    que.push(s);
    vis[s]=1;
    while(que.size()){
        string h=que.front();int o;
        que.pop();
        for(int i=0;i<9;i++){
            if(h[i]=='0'){
                o=i;
                break;
            }
        }
        for(int i=0;i<4;i++){
            if(dx[i]==-1&&(o==3||o==6)){
                continue;
            }
            if(dx[i]==1&&(o==2||o==5)){
                continue;
            }
            int xx=o+dx[i];
            if(xx>=0&&xx<=8){
                string k=h;
                swap(k[o],k[xx]);
                if(vis[k]==0){
                    vis[k]=vis[h]+1;
                    que.push(k);
                }
            }
        }
    }
}
int main(){
	cin>>s;
    bfs();
    cout<<vis["123804765"]-1;
	return 0;
}