http://acm.hdu.edu.cn/showproblem.php?pid=1195
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
    char data[5];
    int step;
};
char st[5],et[5];
int hash[10000];

int getNum(char str[])
{
    return (str[0]-'0')*1000 +(str[1]-'0')*100 + (str[2]-'0')*10 + (str[3]-'0'); 
}

void bfs()
{
    int i,k;
    char tempStr[5],temp;
    Node p,q;
    queue<Node>Q;
    strcpy(p.data,st);
    p.step=0;
    Q.push(p);
    while(!Q.empty())
    {
        q=Q.front();
        Q.pop();
        if(strcmp(q.data,et) == 0)
        {
            cout<<q.step<<endl;
            return ;
        }
        for(i=0;i<4;i++)
        {
            if(i<3)//最后一个时就不用交换了
            {
                   strcpy(tempStr,q.data);
                temp = tempStr[i];
                tempStr[i]=tempStr[i+1];
                tempStr[i+1]=temp;
                   k=getNum(tempStr);
                if(hash[k]==0)
                {
                       hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }
            }

            if(q.data[i]=='1')
            {                
                strcpy(tempStr,q.data);
                tempStr[i]='9';
                k=getNum(tempStr);
                if(hash[k]==0)
                {
                    hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }

                strcpy(tempStr,q.data);
                tempStr[i]='2';
                k=getNum(tempStr);
                if(hash[k]==0)
                {
                    hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }
            }//if(q.data[i]=='1')
            else if(q.data[i]=='9')
            {
                strcpy(tempStr,q.data);
                tempStr[i]='8';
                k=getNum(tempStr);
                if(hash[k]==0)
                {
                    hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }

                strcpy(tempStr,q.data);
                tempStr[i]='1';
                k=getNum(tempStr);
                if(hash[k]==0)
                {
                    hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }
            }//if(q.data[i]=='9')
            else
            {
                strcpy(tempStr,q.data);
                tempStr[i] = tempStr[i] + 1;
                k=getNum(tempStr);
                if(hash[k]==0)
                {
                    hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }

                strcpy(tempStr,q.data);
                tempStr[i] = tempStr[i] - 1;
                k=getNum(tempStr);
                if(hash[k]==0)
                {
                    hash[k]=1;
                    strcpy(p.data,tempStr);
                    p.step = q.step + 1;
                    Q.push(p);
                }
            }//else
        }//for(i=0;i<4;i++)
    }//while(!Q.empty())
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>st>>et;
        memset(hash,0,sizeof(hash));
        bfs();
    }
    return 0;
}