2 1234 2144 1111 9999
2 4
思路：又是一道水题。
#include <stdio.h>
#include <string.h>
#include <cstdlib>
struct{
char num[5];
int step;
}que[1000000],t;
int p[4]={1,10,100,1000};
bool vis[10000];
int main()
{
int T,i,j,len,val,temp;
char des[5];
scanf("%d",&T);
while(T--)
{
scanf("%s%s",que[0].num,des);
int top=0,bottom=1;
que[0].step=0;
memset(vis,0,sizeof vis);
while(top<bottom)
{
t=que[top];
if(strcmp(t.num,des)==0)
{
printf("%d\n",t.step);
break;
}
t.step++;
for(i=0;i<4;i++)
{
if(t.num[i]=='9') t.num[i]='1';
else t.num[i]++;
val=0;
for(j=0;j<4;j++) val=val*10+t.num[j]-'0';
if(!vis[val])
{
vis[val]=1;
que[bottom++]=t;
}
strcpy(t.num,que[top].num);
if(t.num[i]=='1') t.num[i]='9';
else t.num[i]--;
val=0;
for(j=0;j<4;j++) val=val*10+t.num[j]-'0';
if(!vis[val])
{
vis[val]=1;
que[bottom++]=t;
}
strcpy(t.num,que[top].num);
}
for(i=0;i<3;i++)
{
temp=t.num[i];
t.num[i]=t.num[i+1];
t.num[i+1]=temp;
val=0;
for(j=0;j<4;j++) val=val*10+t.num[j]-'0';
if(!vis[val])
{
vis[val]=1;
que[bottom++]=t;
}
temp=t.num[i];
t.num[i]=t.num[i+1];
t.num[i+1]=temp;
}
top++;
}
}
}
HDU-1195-Open the Lock(BFS),布布扣,bubuko.com
原文：http://blog.csdn.net/faithdmc/article/details/38536261