记录

#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 uiop=q.front();
		q.pop();
		for(int i=0;i<9;i++){
			if(uiop.qwq[i]=='0'){
				zx=i;
				break;
			}
		}
		//cout<<"uiop.k: "<<uiop.k<<" uiop.qwq: "<<uiop.qwq<<endl;
		for(int i=0;i<4;i++){
			int op=df[i]+zx;
			if(op<0||op>=9){
				continue;
			}
			string ui=uiop.qwq;
			ui[zx]=ui[op];
			ui[op]='0';
			if(ma[ui]){
				continue;
			}
			if(ui==mb){
				cout<<uiop.k+1<<endl;
				return ;
			}
			ma[ui]=1;
			q.push(jk{uiop.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;
}