#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<stack>
#include<cmath>
using namespace std;
char hashtable[9][9][9][9][9][9][9][9][9];
struct node
{
    int mat[4][4];
    int step;
};
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ans=0;
void bfs()
{
    queue<node> q;
    node now,o,tmp;
    tmp.mat[1][1]=2;tmp.mat[1][2]=9;tmp.mat[1][3]=4;tmp.mat[2][1]=7;tmp.mat[2][2]=5;tmp.mat[2][3]=3;tmp.mat[3][1]=6;tmp.mat[3][2]=1;tmp.mat[3][3]=8;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=2;tmp.mat[1][2]=7;tmp.mat[1][3]=6;tmp.mat[2][1]=9;tmp.mat[2][2]=5;tmp.mat[2][3]=1;tmp.mat[3][1]=4;tmp.mat[3][2]=3;tmp.mat[3][3]=8;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=4;tmp.mat[1][2]=9;tmp.mat[1][3]=2;tmp.mat[2][1]=3;tmp.mat[2][2]=5;tmp.mat[2][3]=7;tmp.mat[3][1]=8;tmp.mat[3][2]=1;tmp.mat[3][3]=6;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=4;tmp.mat[1][2]=3;tmp.mat[1][3]=8;tmp.mat[2][1]=3;tmp.mat[2][2]=5;tmp.mat[2][3]=7;tmp.mat[3][1]=8;tmp.mat[3][2]=1;tmp.mat[3][3]=6;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=6;tmp.mat[1][2]=1;tmp.mat[1][3]=8;tmp.mat[2][1]=7;tmp.mat[2][2]=5;tmp.mat[2][3]=3;tmp.mat[3][1]=2;tmp.mat[3][2]=9;tmp.mat[3][3]=4;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=6;tmp.mat[1][2]=7;tmp.mat[1][3]=2;tmp.mat[2][1]=1;tmp.mat[2][2]=5;tmp.mat[2][3]=9;tmp.mat[3][1]=8;tmp.mat[3][2]=3;tmp.mat[3][3]=4;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=8;tmp.mat[1][2]=1;tmp.mat[1][3]=6;tmp.mat[2][1]=3;tmp.mat[2][2]=5;tmp.mat[2][3]=7;tmp.mat[3][1]=4;tmp.mat[3][2]=9;tmp.mat[3][3]=2;tmp.step=0;
    q.push(tmp);
    tmp.mat[1][1]=8;tmp.mat[1][2]=3;tmp.mat[1][3]=4;tmp.mat[2][1]=1;tmp.mat[2][2]=5;tmp.mat[2][3]=9;tmp.mat[3][1]=6;tmp.mat[3][2]=7;tmp.mat[3][3]=2;tmp.step=0;
    q.push(tmp);
    while(!q.empty())
    {
        now=q.front();q.pop();
        if(hashtable[now.mat[1][1]-1][now.mat[1][2]-1][now.mat[1][3]-1][now.mat[2][1]-1][now.mat[2][2]-1][now.mat[2][3]-1][now.mat[3][1]-1][now.mat[3][2]-1][now.mat[3][3]-1]!=-1)continue;
        hashtable[now.mat[1][1]-1][now.mat[1][2]-1][now.mat[1][3]-1][now.mat[2][1]-1][now.mat[2][2]-1][now.mat[2][3]-1][now.mat[3][1]-1][now.mat[3][2]-1][now.mat[3][3]-1]=now.step;
        for(int i=0;i<4;i++)
        {
            o=now;
            if(1+dx[i]>0&&1+dx[i]<4&&2+dy[i]>0&&2+dy[i]<4)
            {
                swap(o.mat[1+dx[i]][2+dy[i]],o.mat[1][2]);
            }
            o.step++;
            if(hashtable[o.mat[1][1]-1][o.mat[1][2]-1][o.mat[1][3]-1][o.mat[2][1]-1][o.mat[2][2]-1][o.mat[2][3]-1][o.mat[3][1]-1][o.mat[3][2]-1][o.mat[3][3]-1]==-1)q.push(o);
            o=now;
            if(2+dx[i]>0&&2+dx[i]<4&&1+dy[i]>0&&1+dy[i]<4)
            {
                swap(o.mat[2+dx[i]][1+dy[i]],o.mat[2][1]);
            }
            o.step++;
            if(hashtable[o.mat[1][1]-1][o.mat[1][2]-1][o.mat[1][3]-1][o.mat[2][1]-1][o.mat[2][2]-1][o.mat[2][3]-1][o.mat[3][1]-1][o.mat[3][2]-1][o.mat[3][3]-1]==-1)q.push(o);
            o=now;
            if(3+dx[i]>0&&3+dx[i]<4&&2+dy[i]>0&&2+dy[i]<4)
            {
                swap(o.mat[3+dx[i]][2+dy[i]],o.mat[3][2]);
            }
            o.step++;
            if(hashtable[o.mat[1][1]-1][o.mat[1][2]-1][o.mat[1][3]-1][o.mat[2][1]-1][o.mat[2][2]-1][o.mat[2][3]-1][o.mat[3][1]-1][o.mat[3][2]-1][o.mat[3][3]-1]==-1)q.push(o);
            o=now;
            if(2+dx[i]>0&&2+dx[i]<4&&3+dy[i]>0&&3+dy[i]<4)
            {
                swap(o.mat[2+dx[i]][3+dy[i]],o.mat[2][3]);
            }
            o.step++;
            if(hashtable[o.mat[1][1]-1][o.mat[1][2]-1][o.mat[1][3]-1][o.mat[2][1]-1][o.mat[2][2]-1][o.mat[2][3]-1][o.mat[3][1]-1][o.mat[3][2]-1][o.mat[3][3]-1]==-1)q.push(o);
        }
    }
}
int main()
{
    memset(hashtable,-1,sizeof(hashtable));
    node tmp;
    bfs();
    while((scanf("%d",&tmp.mat[1][1]))!=EOF)
    {
        if(scanf("%d",&tmp.mat[1][2])!=EOF)
        if(scanf("%d",&tmp.mat[1][3])!=EOF)
        if(scanf("%d",&tmp.mat[2][1])!=EOF)
        if(scanf("%d",&tmp.mat[2][2])!=EOF)
        if(scanf("%d",&tmp.mat[2][3])!=EOF)
        if(scanf("%d",&tmp.mat[3][1])!=EOF)
        if(scanf("%d",&tmp.mat[3][2])!=EOF)
        if(scanf("%d",&tmp.mat[3][3])!=EOF)
        printf("%d\n",hashtable[tmp.mat[1][1]-1][tmp.mat[1][2]-1][tmp.mat[1][3]-1][tmp.mat[2][1]-1][tmp.mat[2][2]-1][tmp.mat[2][3]-1][tmp.mat[3][1]-1][tmp.mat[3][2]-1][tmp.mat[3][3]-1]);
    }
    return 0;
}

参考了多位大犇的思路 用了bfs+预处理 自己跑了50组数据一般都在1s左右 交上去就TLE……