#include <stdio.h>
#include <stdlib.h>
  
#define tate 3
#define yoko 3
#define Total (tate*yoko)
#define TryCnt 45
 
extern inline void down_0(void);    // 0 を下に移動
extern inline void up_0(void);      // 0 を上に移動
extern inline void right_0(void);   // 0 を右に移動
extern inline void left_0(void);    // 0 を左に移動
 
extern unsigned char serch(unsigned char x, unsigned char y, unsigned char MaxCnt, unsigned char pre);

int num = 0;            // 0 の位置を示す
int val[Total] = {};    // 入力数値を格納
 
 
int main( void )
{
    unsigned int i = 0;
    unsigned int x,y = 0;
     
    // 数値の取り込み
    for(i=0; i<Total; i++)
    {
        scanf("%d",&val[i]);
        
        if(val[i] == 0)
        {
            num = i;
        }
    }
     
    // 0 が右下に行くために 動かさないといけない回数
    x = tate - (num / yoko) -1;
    y = yoko - (num % yoko) -1;
    
    // 解を探す
    for(i=0; i<TryCnt; i++)
    {
        if(serch(x,y,i,4) == 1)
        {
            // 解答を表示
            printf("%d\n",i);
            break;
        }
    }     
     
    return 0;
}
 
unsigned char serch(unsigned char x, unsigned char y, unsigned char MaxCnt, unsigned char pre)
{
    unsigned char result;
    unsigned char i=0;
    
    // 右下に戻れないので打ち切り
    if(MaxCnt < (x + y))
    {
        return 0;
    }
     
    // 最大数でゴールと一致しているか確認
    if(0 == MaxCnt)
    {
        for(i=0; i<Total-1; i++)
        {
            if(val[i] != (i+1))
            {
                // ゴールと不一致
                return 0;
            }
        }
        // ゴールと一致！！
        return 1;
    }
    
    // 0 の移動
    for(i=0; i<4; i++)
    {
        result = 0;
         
        switch(i)
        {
            // 上に移動
            case 0:
                if( (x > 0) && (pre != 3) )
                {
                    down_0();
                     
                    result = serch(x-1, y, MaxCnt-1, 0);
                     
                    up_0();
                }
                break;
                 
            // 右に移動
            case 1:
                if( (y > 0) && (pre != 2) )
                {
                    right_0();
                     
                    result = serch(x, y-1, MaxCnt-1, 1);
                     
                    left_0();
                }
                break;
                
            // 左に移動
            case 2:
                if( (y < yoko -1 ) && (pre != 1) )
                {
                    left_0();
                     
                    result = serch(x, y+1, MaxCnt-1, 2);
                     
                    right_0();
                }
                break;
                
            // 下に移動
            case 3:
                if( (x < tate -1 ) && (pre != 0) )
                {
                    up_0();
                     
                    result = serch(x+1, y, MaxCnt-1, 3);
                     
                    down_0();
                }
                break;
                 
            default:
                // 何もしない。
                break;
        }
         
        if(result)
        {
            return 1;
        }
    }
     
    return 0;
}
 
 
inline void down_0()
{
    val[num] = val[num + yoko];
    num = num + yoko;
}
  
inline void up_0()
{
    val[num] = val[num - yoko];
    num = num - yoko;
}
  
inline void right_0()
{
    val[num] = val[num +1];
    num = num + 1;
}
  
inline void left_0()
{
    val[num] = val[num -1];
    num = num - 1;
}


Measured memory_bytes: 2100