八数码问题实验报告c语言,八数码问题

已结贴√

问题点数：20 回复次数：8

八数码问题

题目：http://acm.hdu.

杭电和北大上有同样的题目，但是杭电的数据比较强，北大的数据弱，我在做杭电的题：

1.用朴素的BFS(TLE)

2.使用预处理，先遍历18W+种情况，然后直接打印路径 如果该start在visit里没有被记录，那么就提示误解    (WA) ：打印出来的路径不对，不知道是什么原因？

做北大的题：

1.用朴素的BFS(RE) 虽然没有TLE，但是评测系统提示数组越界

RQNOJ：

1.用朴素的BFS(AC) 数据很弱吧

朴素BFS：

#include

#include

#include

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

char queue[400000][10];

int s[400000];

char visit[400000];

int farther[400000];

char r[400000];

int fac[9]={1,1,2,6,24,120,720,5040,40320};

void print(int x,int end)

{

if(x==end)

return ;

print(farther[x],end);

printf("%c",r[x]);

}

int judge(int x,int y)

{

if(x>=0&&x<3&&y>=0&&y<3)

return 1;

return 0;

}

int cantor(char s[])

{

int i,j,t,sum=0;

for(i=0;i<9;i++)

{

t=0;

for (j=i+1;j<9;j++)

if(s[j]-'0'

t++;

sum=sum+t*fac[9-i-1];

}

return sum;

}

void bfs(char start[],char end[])

{

int head=0,tail=1;

int i,j,k,x,y,xx,yy,m,step,f;

char temp;

char temp1[10],temp2[3][3];

char temp3[10];

memset(queue,0,sizeof(queue));

memset(visit,0,sizeof(visit));

memset(r,0,sizeof(r));

memset(farther,0,sizeof(farther));

memset(s,0,sizeof(visit));

strcpy(queue[0],start);

while(head

{

strcpy(temp1,queue[head]);

m=0;

for(i=0;i<3;i++)

for(j=0;j<3;j++)

{

temp2[i][j]=temp1[m++];

if(temp2[i][j]=='0')

x=i,y=j;

}

step=s[head];

if(strcmp(temp1,end)==0)

{

print(cantor(end),cantor(start));

//printf(" %dn",step);

printf("n");

return ;

}

head++;

for(i=0;i<4;i++)

{

xx=x+dx[i];

yy=y+dy[i];

m=0;

for(k=0;k<3;k++)

for(j=0;j<3;j++)

temp2[k][j]=temp1[m++];

if(judge(xx,yy)==1)

{

temp=temp2[xx][yy];

temp2[xx][yy]=temp2[x][y];

temp2[x][y]=temp;

m=0;

for(k=0;k<3;k++)

for(j=0;j<3;j++)

temp3[m++]=temp2[k][j];

f=cantor(temp3);

if(visit[f]==1)

continue;

visit[f]=1;

farther[f]=cantor(temp1);

if(i==0)

r[f]='u';

else if(i==1)

r[f]='r';

else if(i==2)

r[f]='d';

else

r[f]='l';

strcpy(queue[tail],temp3);

s[tail]=step+1;

tail++;

continue;

}

}

}

printf("unsolvablen");

}

int main()

{

int i,m;

char temp[1000];

char start[10],end[10];

while(gets(temp))

{

for(i=0,m=0;i

if((temp[i]>='0'&&temp[i]<='9')||temp[i]=='x')

{

if(temp[i]!='x')

start[m++]=temp[i];

else

start[m++]='0';

}

strcpy(end,"123456780");

bfs(start,end);

}

//system("pause");

return 0;

}

预处理BFS：

#include

#include

#include

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

char queue[400000][10];

char visit[400000];

int farther[400000];

char r[400000];

int fac[9]={1,1,2,6,24,120,720,5040,40320};

void print(int x,int end)

{

if(x==end)

return ;

print(farther[x],end);

printf("%c",r[x]);

}

int judge(int x,int y)

{

if(x>=0&&x<3&&y>=0&&y<3)

return 1;

return 0;

}

int cantor(char s[])

{

int i,j,t,sum=0;

for(i=0;i<9;i++)

{

t=0;

for (j=i+1;j<9;j++)

if(s[j]-'0'

t++;

sum=sum+t*fac[9-i-1];

}

return sum;

}

void bfs()

{

int head=0,tail=1;

int i,j,k,x,y,xx,yy,m,f;

char temp;

char temp1[10],temp2[3][3];

char temp3[10];

memset(queue,0,sizeof(queue));

memset(visit,0,sizeof(visit));

memset(r,0,sizeof(r));

memset(farther,0,sizeof(farther));

strcpy(queue[0],"123456780");

while(head

{

strcpy(temp1,queue[head]);

m=0;

for(i=0;i<3;i++)

for(j=0;j<3;j++)

{

temp2[i][j]=temp1[m++];

if(temp2[i][j]=='0')

x=i,y=j;

}

head++;

/*for(i=0;i<3;i++)

{

printf("n");

for(j=0;j<3;j++)

printf("%c",temp2[i][j]);

}

printf("n");*/

for(i=0;i<4;i++)

{

xx=x+dx[i];

yy=y+dy[i];

m=0;

for(k=0;k<3;k++)

for(j=0;j<3;j++)

temp2[k][j]=temp1[m++];

if(judge(xx,yy)==1)

{

temp=temp2[xx][yy];

temp2[xx][yy]=temp2[x][y];

temp2[x][y]=temp;

m=0;

memset(temp3,0,sizeof(temp3));

for(k=0;k<3;k++)

for(j=0;j<3;j++)

temp3[m++]=temp2[k][j];

f=cantor(temp3);

if(visit[f]==1)

continue;

visit[f]=1;

farther[f]=cantor(temp1);

if(i==0)

r[f]='u';

else if(i==1)

r[f]='r';

else if(i==2)

r[f]='d';

else

r[f]='l';

strcpy(queue[tail],temp3);

tail++;

continue;

}

}

}

//printf("-1n");

}

int main()

{

int i,m;

char temp[50];

char start[10],end[10];

bfs();

strcpy(end,"123456780");

while(gets(temp))

{

for(i=0,m=0;i

if((temp[i]>='0'&&temp[i]<='9')||temp[i]=='x')

{

if(temp[i]!='x')

start[m++]=temp[i];

else

start[m++]='0';

}

if(visit[cantor(start)]==1)

{

print(cantor(start),cantor(end));

printf("n");

}

else

printf("unsolvablen");

}

//system("pause");

return 0;

}