记录

#include<bits/stdc++.h>
using namespace std;
const string mb="123804765";
map<string,bool>ma;
int df[4]={1,-1,3,-3};
struct jk{
	int k;
	string qwq;
};
void bfs(string s){
	queue<jk>q;
	int zx;
	q.push(jk{0,s});
	while(!q.empty()){
		jk op=q.front();
		q.pop();
		for(int i=0;i<9;i++){//找0 
			if(op.qwq[i]=='0'){
				zx=i;
				break;
			}
		}
		for(int i=0;i<4;i++){//上下左右查找 
			int er=df[i]+zx;
			if(er<0||er>=9){
				continue;
			}
			string ui=op.qwq;
			ui[zx]=ui[er];
			ui[er]='0';
			if(ma[ui]){
				continue;
			}
			//cout<<" k: "<<op.k+1<<" ui: "<<ui<<" qwq: "<<op.qwq<<endl; 
			if(ui==mb){
				cout<<op.k+1<<endl;
				return ;
			}
			ma[ui]=1;
			q.push(jk{op.k+1,ui});
		}
	}
	return ;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	bfs(s);
	return 0;
}