ACM--HDU 1195 Open the Lock 小BFS
弄了一上午了 总是不对
http://acm.hdu.edu.cn/showproblem.php?pid=1195
题目大意：给出原密码和准确密码，对于原密码每次可以进行三个操作：
1：任意一位+1 且9+1=1
2：任意一位-1 且1-1=9
3：相邻两位互换，且首位和末位不是相邻的。
（密码只有四位数，每个数字1-9） 题目要求原密码变成准确密码的最少步数
我的代码
#include<stdio.h>
#include<string.h>
struct Node
{
char str[5];//每种的字符串
int ti;//每种的移动次数
}dui[6700];//9^4
char pass[5];
int bfs();
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",dui[0].str);
scanf("%s",pass);
printf("%d\n",bfs());
}
return 0;
}
int bfs()
{
int head,tail,flag,i,j,now;
char tem[12][5],ch;
head=tail=0;
dui[0].ti=0;
tail++;
while(head<tail)
{
now=head++;//出队
for(i=0;i<11;i++)
{
flag=0;
strcpy(tem[i],dui[now].str);
if(i<=2)//临位互换
{
ch=tem[i][i];
tem[i][i]=tem[i][i+1];
tem[i][i+1]=ch;
}
if(i>=3 && i<=6)//+1
{
if(tem[i][i-3]<'9') tem[i][i-3]+=1;
else tem[i][i-3]='1';
}
if(i>=7 && i<=10)//-1
{
if(tem[i][i-7]>'1') tem[i][i-7]-=1;
else tem[i][i-7]='9';
}
if(strcmp(tem[i],pass)==0) return (dui[now].ti+1);
for(j=0;j<now;j++)
{
if(strcmp(tem[i],dui[j].str)==0)
{
flag=1;break;
}
}
if(flag==0)
{
dui[tail].ti=dui[now].ti+1;
strcpy(dui[tail++].str,tem[i]);//入队
// puts(dui[tail-1].str);
}
}
}
return -1;
}
