魔板
题目：http://acm.hdu.应该来说这题是道八数码的另一种形式，我这次试着用双广（不知道对于这题还有没有比双向广搜更好的方法），A*貌似是不行的，写完以后发现WA，然后找了几个数据发现打印出来的步数就有问题（而且错误的结果和正确的结果大概相差1到2步）:
只要给我看看大概的双向广搜实现的对不对就行了，不用看里面的3个生成状态
head1，head2为两个头指针
tail1，tail2为两个尾指针
now为层数（只有按层扩展才能保证结果是正确的）
测试一：
31246578
13246875
正确输出：
18
测试二：
56123487
12345678
正确输出：
20
CODE：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int fac[9]={1,1,2,6,24,120,720,5040,40320};
char queue1[400000][9];
char queue2[400000][9];
int visit1[400000];
int visit2[400000];
int s1[400000];
int s2[400000];
int head1,tail1,head2,tail2,now;
int cantor(char s[])
{
int i,j,t,sum=0;
for(i=0;i<8;i++)
{
t=0;
for (j=i+1;j<8;j++)
if(s[j]-'0'<s[i]-'0')
t++;
sum=sum+t*fac[8-i-1];
}
return sum;
}
int bfs1()
{
char temp,temp1[9],temp2[9],temp3[2][4];
memset(temp2,0,sizeof(temp2));
int i,j,f,step;
strcpy(temp1,queue1[head1]);
step=s1[head1];
head1++;
strcpy(temp2,temp1);
strrev(temp2);
f=cantor(temp2);
if(visit2[f]!=-1)
return step+visit2[f]+1;
if(visit1[f]==-1)
{
visit1[f]=step+1;
strcpy(queue1[tail1],temp2);
s1[tail1]=step+1;
tail1++;
}
strcpy(temp2,temp1);
temp=temp2[3];
for(i=3;i>=1;i--)
temp2[i]=temp2[i-1];
temp2[0]=temp;
temp=temp2[4];
for(i=4;i<=7;i++)
temp2[i]=temp2[i+1];
temp2[7]=temp;
f=cantor(temp2);
if(visit2[f]!=-1)
return step+visit2[f]+1;
if(visit1[f]==-1)
{
visit1[f]=step+1;
strcpy(queue1[tail1],temp2);
s1[tail1]=step+1;
tail1++;
}
strcpy(temp2,temp1);
for(i=0;i<4;i++)
temp3[0][i]=temp2[i];
for(i=7,j=0;i>=4;i--)
temp3[1][j++]=temp2[i];
temp=temp3[0][1];
temp3[0][1]=temp3[1][1];
temp3[1][1]=temp3[1][2];
temp3[1][2]=temp3[0][2];
temp3[0][2]=temp3[0][1];
temp3[0][2]=temp;
for(i=0;i<4;i++)
temp2[i]=temp3[0][i];
for(i=7,j=0;i>=4;i--)
temp2[i]=temp3[1][j++];
f=cantor(temp2);
if(visit2[f]!=-1)
return step+visit2[f]+1;
if(visit1[f]==-1)
{
visit1[f]=step+1;
strcpy(queue1[tail1],temp2);
s1[tail1]=step+1;
tail1++;
}
return 0;
}
int bfs2()
{
char temp,temp1[9],temp2[9],temp3[2][4];
int i,j,f,step;
strcpy(temp1,queue2[head2]);
step=s2[head2];
head2++;
strcpy(temp2,temp1);
strrev(temp2);
f=cantor(temp2);
if(visit1[f]!=-1)
return step+visit1[f]+1;
if(visit2[f]==-1)
{
visit2[f]=step+1;
strcpy(queue2[tail2],temp2);
s2[tail2]=step+1;
tail2++;
}
strcpy(temp2,temp1);
temp=temp2[3];
for(i=3;i>=1;i--)
temp2[i]=temp2[i-1];
temp2[0]=temp;
temp=temp2[4];
for(i=4;i<=7;i++)
temp2[i]=temp2[i+1];
temp2[7]=temp;
f=cantor(temp2);
if(visit1[f]!=-1)
return step+visit1[f]+1;
if(visit2[f]==-1)
{
visit2[f]=step+1;
strcpy(queue2[tail2],temp2);
s2[tail2]=step+1;
tail2++;
}
strcpy(temp2,temp1);
for(i=0;i<4;i++)
temp3[0][i]=temp2[i];
for(i=7,j=0;i>=4;i--)
temp3[1][j++]=temp2[i];
temp=temp3[0][1];
temp3[0][1]=temp3[1][1];
temp3[1][1]=temp3[1][2];
temp3[1][2]=temp3[0][2];
temp3[0][2]=temp3[0][1];
temp3[0][2]=temp;
for(i=0;i<4;i++)
temp2[i]=temp3[0][i];
for(i=7,j=0;i>=4;i--)
temp2[i]=temp3[1][j++];
f=cantor(temp2);
if(visit1[f]!=-1)
return step+visit1[f]+1;
if(visit2[f]==-1)
{
visit2[f]=step+1;
strcpy(queue2[tail2],temp2);
s2[tail2]=step+1;
tail2++;
}
return 0;
}
int bbfs(char start[],char end[])
{
int ans=-1;
head1=0,tail1=1,head2=0,tail2=1,now=0;
memset(visit1,-1,sizeof(visit1));
memset(visit2,-1,sizeof(visit2));
memset(queue1,0,sizeof(queue1));
memset(queue2,0,sizeof(queue2));
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
strcpy(queue1[0],start);
strcpy(queue2[0],end);
visit1[cantor(start)]=0;
visit2[cantor(end)]=0;
while(head1<tail1||head2<tail2)
{
while(head1<tail1&&visit1[cantor(queue1[head1])]==now)
{
ans=bfs1();
if(ans!=0)
return ans;
}
while(head2<tail2&&visit2[cantor(queue2[head2])]==now)
{
ans=bfs2();
if(ans!=0)
return ans;
}
now++;
}
return -1;
}
int main()
{
char start[9],end[9];
int t,ans;
scanf("%d",&t);
while(t>=1)
{
scanf("%s",start);
scanf("%s",end);
if(strcmp(start,end)==0)
{
printf("0\n");
t--;
continue;
}
ans=bbfs(start,end);
printf("%d\n",ans);
t--;
}
system("pause");
return 0;
}
