描述：坑人的一道题，不过也不难，就是数字交换，只有一正一负的数字才存在交换，并且交换之后不能形成素数
#include
#include
#include
#define N 1000003
int t[10]= {1,2,3,4,5,6,7,8},cmp[]= {4,6,8,9,10,12,14,15};
int head[N],next[N],count[N];
int str[N][10][2];
int m=1,sum,flag;
int hash(int (*p)[2])
{
int x=0;
for(int i=0; i<8; i++)
x=(x*10+p[i][0])%N;
return x;
}
bool insert(int x,int rear)
{
int c=head[x];
while(c!=-1)
{
int z=0;
for(int i=0; i<8; i++)
if(str[rear][i][0]!=str[c][i][0])
{
z=1;
break;
}
if(z) c=next[c];
else return false;
}
next[rear]=head[x];
head[x]=rear;
return true;
}
void bfs()
{
memset(head,-1,sizeof(head));
memset(next,-1,sizeof(next));
memset(count,0,sizeof(count));
flag=0;
int rear=1,front=0;
while(front
{
for(int i=0; i<8; i++)
for(int j=0; j<8; j++)
if(str[front][j][1]+str[front][i][1]==1)
{
int c=0;
for(int k=0; k<8; k++) if(str[front][i][0]+str[front][j][0]==cmp[k])
{
c=-1;
break;
}
if(c!=-1)//前插
{
if(j>i)
{
for(int k=0; k
{
str[rear][k][0]=str[front][k][0];
str[rear][k][1]=str[front][k][1];
}
for(int k=j; k<8; k++)
{
str[rear][k][0]=str[front][k][0];
str[rear][k][1]=str[front][k][1];
}
for(int k=i; k
{
str[rear][k][0]=str[front][k+1][0];
str[rear][k][1]=str[front][k+1][1];
}
str[rear][j-1][0]=str[front][i][0];
str[rear][j-1][1]=str[front][i][1];
}
else
{
for(int k=0; k
{
str[rear][k][0]=str[front][k][0];
str[rear][k][1]=str[front][k][1];
}
for(int k=i+1; k<8; k++)
{
str[rear][k][0]=str[front][k][0];
str[rear][k][1]=str[front][k][1];
}
for(int k=i; k>j; k--)
{
str[rear][k][0]=str[front][k-1][0];
str[rear][k][1]=str[front][k-1][1];
}
str[rear][j][0]=str[front][i][0];
str[rear][j][1]=str[front][i][1];
}
for(int k=0; k<8; k++) if(str[rear][k][0]!=t[k])
{
flag=1;
break;
}
if(!flag)
{
sum=count[front]+1;
return;
}
else
{
flag=0;
int x=hash(str[rear]);
if(insert(x,rear))
{
count[rear]=count[front]+1;
rear++;
}