paste bin

#include <cstdio>
#include <cstring>
#include <set>
using std::set;
#include <queue>
using std::queue;

int str2int(char*);
void num2Graph(int);
int moveUp(int);
int moveDown(int);
int moveLeft(int);
int moveRight(int);
int solve(int);
int inversions(char*);
struct numNode
{
    int level;
    int val;
};

int main(void)
{
    int IDX,i,N,v;
    N=1;
    char s[10];
    for(IDX=1;IDX<=N;IDX++)
    {
        for(i=0;i<9;i++)
            scanf("%s",s+i);
        s[9]=0;
        if(inversions(s)%2==0)
        {
            v=str2int(s); 
            printf("%d\n",solve(v) );
        }
        else
        {
            printf("impossible\n");
        }
    }
    return 0;
}

int inversions(char* s)
{
    int count,i,j;
    count=0;
    for(i=1;i<9;i++)
    {
        for(j=0;j<i;j++)
        {
            if(s[j]=='0')
                continue;
            if(s[j]<s[i])
                count++;
        }
    }
    return count;
}

int solve(int v)
{
    set<int> used;
    queue<numNode> q;
    int (*move[4])(int)={moveUp,moveDown,moveLeft,moveRight};
    int nextXVal,brkFlag,k,res;
    numNode x,nextX;
    x.level=0;
    x.val=v;
    q.push(x);
    used.insert(x.val);
    brkFlag=1;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        if(x.val==123456780)
        {
            res=x.level;
            break;
        }
        for(k=0;k<4;k++)
        {
            nextXVal=move[k](x.val);
            nextX.level=x.level+1;
            if(nextXVal==123456780)
            {
                brkFlag=0;
                res=nextX.level;
                break;
            }
            if(used.count(nextXVal)==0)
            {
                nextX.val=nextXVal;
                q.push(nextX);
                used.insert(nextXVal);
            }
        }
        if(brkFlag==0)
            break;
    }
    return res;
}

int str2int(char* s)
{
    int i,x=0;    
    for(i=0;i<9;i++)
    {
        x=x*10+s[i]-'0';
    }
    return x;
}

int moveUp(int x)
{
    char s[10];
    int tt,k;
    tt=1;
    for(k=8;k>=0;--k)
    {
        s[k]='0'+x%(10*tt)/tt;
        tt*=10;            
    }    
    int tmp,pos0,posZ;
    pos0=strchr(s,'0')-s;
    posZ=pos0-3;
    if(posZ>=0)
    {    
        tmp=s[pos0];
        s[pos0]=s[posZ];
        s[posZ]=tmp;
    }
    return str2int(s);
}

int moveDown(int x)
{
    char s[10];
    int tt,k;
    tt=1;
    for(k=8;k>=0;--k)
    {
        s[k]='0'+x%(10*tt)/tt;
        tt*=10;            
    }    
    int tmp,pos0,posZ;
    pos0=strchr(s,'0')-s;
    posZ=pos0+3;
    if(posZ<9) 
    {
        tmp=s[pos0];
        s[pos0]=s[posZ];
        s[posZ]=tmp;
    }
    return str2int(s);
}

int moveLeft(int x)
{
    char s[10];
    int tt,k;
    tt=1;
    for(k=8;k>=0;--k)
    {
        s[k]='0'+x%(10*tt)/tt;
        tt*=10;            
    }
    int tmp,pos0,posZ;
    pos0=strchr(s,'0')-s;
    posZ=pos0-1;
    if(posZ>=0 && posZ%3<2) 
    {
        tmp=s[pos0];
        s[pos0]=s[posZ];
        s[posZ]=tmp;
    }
    return str2int(s);
}

int moveRight(int x)
{
    char s[10];
    int tt,k;
    tt=1;
    for(k=8;k>=0;--k)
    {
        s[k]='0'+x%(10*tt)/tt;
        tt*=10;            
    }
    int tmp,pos0,posZ;
    pos0=strchr(s,'0')-s;
    posZ=pos0+1;
    if(posZ%3>0) 
    {
        tmp=s[pos0];
        s[pos0]=s[posZ];
        s[posZ]=tmp;
    }
    return str2int(s);
}