hdu1195: 题意：求解密最少步骤：密码为四位数，每次操作可将一个数加一或减一（1减一变为9，9加一变为1），也可互换相邻数字，求最少需要多少操作数能解密解法：bfs:加一减一和交换位置都属于状态转移 code:
#include#include #include int q[1000*1000][4],v[4],key[4],dis[10][10][10][10],an1[4],bn1[4],cn1[4],dn1[4],an2[4],bn2[4],cn2[4],dn2[4],an[4],bn[4],cn[4],dn[4];const int inf=1<<29;int main(){ int t,i,j,rear,front,a,b,c,d,tt,ttt; scanf("%d",&t); while(t--) { for(i=0;i<=9;i++) for(j=0;j<=9;j++) for(int x=0;x<=9;x++) for(int y=0;y<=9;y++) dis[i][j][x][y]=inf; rear=0;front=0; scanf("%d",&tt); for(j=3;j>=0;j--) { v[j]=tt%10; q[rear][j]=v[j]; tt=tt/10; } rear++; dis[v[0]][v[1]][v[2]][v[3]]=0; scanf("%d",&ttt); for(j=3;j>=0;j--) { key[j]=ttt%10; ttt=ttt/10; } getchar(); while(rear>front) { a=q[front][0];b=q[front][1];c=q[front][2];d=q[front++][3]; for(i=0;i<4;i++) { if(i==0) { if(a==1) { an1[0]=9;bn1[0]=b;cn1[0]=c;dn1[0]=d; an2[0]=2;bn2[0]=b;cn2[0]=c;dn2[0]=d; } else if(a==9) { an1[0]=1;bn1[0]=b;cn1[0]=c;dn1[0]=d; an2[0]=8;bn2[0]=b;cn2[0]=c;dn2[0]=d; } else { an1[0]=a-1;bn1[0]=b;cn1[0]=c;dn1[0]=d; an2[0]=a+1;bn2[0]=b;cn2[0]=c;dn2[0]=d; } } if(i==1) { if(b==1) { an1[1]=a;bn1[1]=9;cn1[1]=c;dn1[1]=d; an2[1]=a;bn2[1]=2;cn2[1]=c;dn2[1]=d; } else if(b==9) { an1[1]=a;bn1[1]=1;cn1[1]=c;dn1[1]=d; an2[1]=a;bn2[1]=8;cn2[1]=c;dn2[1]=d; } else { an1[1]=a;bn1[1]=b-1;cn1[1]=c;dn1[1]=d; an2[1]=a;bn2[1]=b+1;cn2[1]=c;dn2[1]=d; } } if(i==2) { if(c==1) { an1[2]=a;bn1[2]=b;cn1[2]=9;dn1[2]=d; an2[2]=a;bn2[2]=b;cn2[2]=2;dn2[2]=d; } else if(c==9) { an1[2]=a;bn1[2]=b;cn1[2]=1;dn1[2]=d; an2[2]=a;bn2[2]=b;cn2[2]=8;dn2[2]=d; } else { an1[2]=a;bn1[2]=b;cn1[2]=c-1;dn1[2]=d; an2[2]=a;bn2[2]=b;cn2[2]=c+1;dn2[2]=d; } } if(i==3) { if(d==1) { an1[3]=a;bn1[3]=b;cn1[3]=c;dn1[3]=9; an2[3]=a;bn2[3]=b;cn2[3]=c;dn2[3]=2; } else if(d==9) { an1[3]=a;bn1[3]=b;cn1[3]=c;dn1[3]=1; an2[3]=a;bn2[3]=b;cn2[3]=c;dn2[3]=8; } else { an1[3]=a;bn1[3]=b;cn1[3]=c;dn1[3]=d-1; an2[3]=a;bn2[3]=b;cn2[3]=c;dn2[3]=d+1; } } if(dis[an1[i]][bn1[i]][cn1[i]][dn1[i]]>dis[a][b][c][d]+1) { dis[an1[i]][bn1[i]][cn1[i]][dn1[i]]=dis[a][b][c][d]+1; q[rear][0]=an1[i];q[rear][1]=bn1[i];q[rear][2]=cn1[i];q[rear++][3]=dn1[i]; } if(dis[an2[i]][bn2[i]][cn2[i]][dn2[i]]>dis[a][b][c][d]+1) { dis[an2[i]][bn2[i]][cn2[i]][dn2[i]]=dis[a][b][c][d]+1; q[rear][0]=an2[i];q[rear][1]=bn2[i];q[rear][2]=cn2[i];q[rear++][3]=dn2[i]; } } an[0]=b;bn[0]=a;cn[0]=c;dn[0]=d; an[1]=a;bn[1]=c;cn[1]=b;dn[1]=d; an[2]=a;bn[2]=b;cn[2]=d;dn[2]=c; for(i=0;i<3;i++) { if(dis[an[i]][bn[i]][cn[i]][dn[i]]>dis[a][b][c][d]+1) { dis[an[i]][bn[i]][cn[i]][dn[i]]=dis[a][b][c][d]+1; q[rear][0]=an[i];q[rear][1]=bn[i];q[rear][2]=cn[i];q[rear++][3]=dn[i]; } } } printf("%d\n",dis[key[0]][key[1]][key[2]][key[3]]); }}/*input:21234214411119999output:24*/