题目大意：给你一个4位数的初始状态（只包含1~9），要求你变化成另一个4位数。

变化规则为：每次可给任意一位加1或减1（1减1变为9,9加1变为1），或交换相邻两个数位上的数字（第一位和最后一位不相邻）。

要你求出最少的变化次数。

解题思路：这道题很明显是一道BFS的题，只不过变化的操作复杂了点。我使用了字符串进行处理。

一开始我用的是STL的string，后来我改成了C字符串，对比如下：

 

这充分说明了string的慢。。

操作虽然复杂，但耐心点还是能写好的。

具体见代码。

C++ Code:

#include
     
      #include
      
       #include
       
        using namespace std;char n[5],m[5];struct sss{    int a;    char s[5];};sss d[9002];bool b[10001];const int dd[]={1,-1};void bfs(){    int l=0,r=1;    memset(b,0,sizeof(b));    d[1].a=0;    strcpy(d[1].s,n);    while(l!=r){        l=l%9000+1;        for(int i=0;i<4;i++)        for(int j=0;j<3;j++)        if(j!=2){            char c[5];            strcpy(c,d[l].s);            c[i]+=dd[j];            if(c[i]=='0')c[i]='9';            if(c[i]>'9')c[i]='1';            int f=atoi(c);            if(!b[f]){                b[f]=1;                r=r%9000+1;                strcpy(d[r].s,c);                d[r].a=d[l].a+1;                if(strcmp(c,m)==0){                	printf("%d\n",d[r].a);                    return;                }            }        }else{            for(int k=0;k<=2;k++){                char c[5];                strcpy(c,d[l].s);                char f=c[k];                c[k]=c[k+1];                c[k+1]=f;                int ll=atoi(c);            if(!b[ll]){                b[ll]=1;                r=r%9000+1;                strcpy(d[r].s,c);                d[r].a=d[l].a+1;                if(strcmp(c,m)==0){                	printf("%d\n",d[r].a);                    return;                }            }            }        }    }}int main(){    int o;    scanf("%d",&o);    while(o--){    	scanf("%s",n);    	scanf("%s",m);        if(strcmp(n,m)==0){            puts("0");            continue;        }        bfs();    }}