//code by Dreamer_002
//20250629
#include<cstdio>
#include<cstring>
const int goal[4][4]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};
const int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
char str[10];
int mp[5][5],ceng,okans,sx,sy;
int exchange(int& x,int& y);
int check();
int checkk(int step);
void dfs(int step,int x,int y,int last);
int main(){
    scanf("%s",str);
    for(int i=0;i<9;i++){
    	int xx=i/3+1;
    	int yy=i%3+1;
        mp[xx][yy]=str[i]-'0';
        if(str[i]=='0'){
        	sx=xx;
			sy=yy;
		}
    }
    if(check()==1){
		printf("0\n");
		return 0;
	}
    while(1){
    	ceng++;
        dfs(0,sx,sy,-1);
        if(okans==1){
			printf("%d\n",ceng);
			return 0;
		}
    }
    return 0;
}
int exchange(int& x,int& y){
	int t=x;x=y;y=t;
}
int check(){
    for(int i=1;i<=3;i++){
	    for(int j=1;j<=3;j++){
		    if(goal[i][j]!=mp[i][j]){
		    	return 0;
			}
		}
	}
    return 1;
}
int checkk(int step){
    int tot=0;
    for(int i=1;i<=3;i++){
	    for(int j=1;j<=3;j++){
		    if(goal[i][j]!=mp[i][j]){
				if(++tot+step>ceng){
					return 0;
				}
			}
		}
	}
    return 1;
}
void dfs(int step,int x,int y,int last){
    if(step==ceng){
		if(check()==1){
			okans=1;
		}
		return ;
	}
	if(okans==1){
		return ;
	}
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
		int yy=y+dy[i];
        if(xx<1 || xx>3 || yy<1 || yy>3 || last+i==3){
			continue;
		}
        exchange(mp[x][y],mp[xx][yy]);
        if(checkk(step)==1 && okans==0){
        	dfs(step+1,xx,yy,i);
		}
        exchange(mp[x][y],mp[xx][yy]);
    }
}

中

if(++tot+step>ceng){//为什么变为(++tot)不行
    return 0;
}