做题感悟：
第一次做这题时用的是单向广搜，用的最笨的方法，把所有情况都列出来了。这一星期搞了一下双向广搜，百度了一下这题可以用双向广搜，正好借这题学一下双向广搜，学完才发现原来双向广搜广搜这么简单。
题意：
给你两个四位数的整数，让你从第一个经过若干次变化变成第二个。可以进行的操作：某一位减一（如果是 1，则变成 9 ），某一位加一（如果是 9 ，则变成 1 ），还可以交换相邻两位（第一位与第四位不相邻）。
解题思路：
每一位都进行：加一，减一，交换的操作（和暴力差不多）。
代码（双广）：
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std ;
char s1[8],s2[8] ;
int vis1[15][15][15][15],vis2[15][15][15][15] ;
struct zhang
{
int x[8],step ;
} ;
int bbfs()
{
queue<zhang>q1,q2 ;
zhang curt,next ;
memset(vis1,-1,sizeof(vis1)) ;
memset(vis2,-1,sizeof(vis2)) ;
curt.step=0 ;
next.step=0 ;
for(int i=0 ;i<4 ;i++)
{
curt.x[i]=s1[i]-'0' ;
next.x[i]=s2[i]-'0' ;
}
vis1[curt.x[0]][curt.x[1]][curt.x[2]][curt.x[3]]=0 ;
vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=0 ;
q1.push(curt) ;
q2.push(next) ;
int temp1=0,temp2=0,k ;
while(1)
{
while(!q1.empty()&&temp1==q1.front().step)
{
curt=q1.front() ;
q1.pop() ;
if((k=vis2[curt.x[0]][curt.x[1]][curt.x[2]][curt.x[3]])!=-1)
{
return curt.step+k ;
}
curt.step=curt.step+1 ;
for(int i=0 ;i<4 ;i++) // 加一和减一
{
next=curt ;
if(curt.x[i]==9)
next.x[i]=1 ;
else next.x[i]=curt.x[i]+1 ;
if((k=vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]])!=-1)
return next.step+k ;
if(vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]]==-1)
{
vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=next.step ;
q1.push(next) ;
}
if(curt.x[i]==1)
next.x[i]=9 ;
else next.x[i]=curt.x[i]-1 ;
if((k=vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]])!=-1)
return next.step+k ;
if(vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]]==-1)
{
vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=next.step ;
q1.push(next) ;
}
}
for(int i=0 ;i<3 ;i++) // 相邻的交换
{
next=curt ;
next.x[i]=curt.x[i+1] ;
next.x[i+1]=curt.x[i] ;
if((k=vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]])!=-1)
return next.step+k ;
if(vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]]==-1)
{
vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=next.step ;
q1.push(next) ;
}
}
}
temp1=q1.front().step ;
while(!q2.empty()&&temp2==q2.front().step) // 反向搜索
{
curt=q2.front() ;
q2.pop() ;
if((k=vis1[curt.x[0]][curt.x[1]][curt.x[2]][curt.x[3]])!=-1)
{
return curt.step+k ;
}
curt.step=curt.step+1 ;
for(int i=0 ;i<4 ;i++) // 加一和减一
{
next=curt ;
if(curt.x[i]==9) // 加一
next.x[i]=1 ;
else next.x[i]=curt.x[i]+1 ;
if((k=vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]])!=-1)
return next.step+k ;
if(vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]==-1)
{
vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=next.step ;
q2.push(next) ;
}
if(curt.x[i]==1) // 减一
next.x[i]=9 ;
else next.x[i]=curt.x[i]-1 ;
if((k=vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]])!=-1)
return next.step+k ;
if(vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]==-1)
{
vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=next.step ;
q2.push(next) ;
}
}
for(int i=0 ;i<3 ;i++) // 相邻的交换
{
next=curt ;
next.x[i]=curt.x[i+1] ;
next.x[i+1]=curt.x[i] ;
if((k=vis1[next.x[0]][next.x[1]][next.x[2]][next.x[3]])!=-1)
return next.step+k ;
if(vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]==-1)
{
vis2[next.x[0]][next.x[1]][next.x[2]][next.x[3]]=next.step ;
q2.push(next) ;
}
}
}
temp2=q2.front().step ;
}
}
int main()
{
int T ;
scanf("%d",&T) ;
while(T--)
{
scanf("%s%s",s1,s2) ;
printf("%d\n",bbfs()) ;
}
return 0 ;
}