八数码广度优先算法题解C++

//主要思想是把每一个序列按字典序排序,那么每一个序列就会有一个固定的序列号,这个序列号是可以计算的,序列直接存下来.我是计算出来的.然后再去广搜,从起点开始搜.
#include
#include
int exist[363000];
int fac[10]={1};
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int rank(const int n[])
{
int sum,i,ans=0,j,used[10]={0};
for(i=0;i<9;i++)
{
sum=0;
for(j=1;j if(used[j])
sum++;
ans+=(n[i]-1-sum)*fac[9-i-1];
used[n[i]]=1;
}
return ans;
}
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void BFS()
{
int front=-1,rear=0,i,size,step=0;
int queue[363000]={123456789},t,j;
int temp[3][3],k,matrix[3][3],x,y,tx,ty;
int n[10],ans,sum,u;
memset(exist,-1,sizeof(exist));
exist[0]=0;
while(front {
size=rear-front;
step++;
while(size--)
{
front++;
t=queue[front];
i=0;
j=0;
while(t)
{
matrix[i][j]=t%10;
t/=10;
j++;
if(j%3==0&&j>0)
{
i++;
j=0;
}
}

swap(&matrix[0][0],&matrix[2][2]);
swap(&matrix[0][1],&matrix[2][1]);
swap(&matrix[0][2],&matrix[2][0]);
swap(&matrix[1][0],&matrix[1][2]);

for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(matrix[i][j]==9)
{
x=i;
y=j;
break;
}

for(i=0;i<4;i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(!(tx>=0&&tx<3&&ty>=0&&ty<3))
continue;

for(j=0;j<3;j++)
{
for(k=0;k<3;k++)
temp[j][k]=matrix[j][k];
}
k=temp[x][y];
temp[x][y]=temp[tx][ty];
temp[tx][ty]=k;
for(k=u=0;u<3;u++)
{
for(j=0;j<3;j++,k++)
n[k]=temp[u][j];
}
ans=rank(n);
if(exist[ans]>-1)
continue;

exist[ans]=step;
sum=0;
for(u=0;u<9;u++)
sum=sum*10+n[u];
rear++;
queue[rear]=sum;
}
}
}
}
main()
{
int i,n,temp[10],ans,j;
char s[100];
for(i=1;i<10;i++)
fac[i]=fac[i-1]*i;
BFS();
while(gets(s))
{
for(j=0,i=0;s[i]!='\0';i++)
{
if(s[i]!=' ')
{
if(s[i]!='x')
temp[j++]=s[i]-'0';
else
temp[j++]=9;
}
}
ans=rank(temp);
if(exist[ans]==-1)
printf("unsolveable\n");
else
printf("%d\n",exist[ans]);
}
}