八数码c语言代码

1、八数码c语言代码#in clude<stdio.h>#in clude<stdlib.h> #in clude<memory.h> struct no deint x,y;int cn tdif;int step;int f9;int xy33; queue10000;int map 33;int dir42=-1,0,1,0,0,1,0,-1;int hash10000;int zz9;int f1,f2;struct node sour,dest;int judge( int a)/用逆序数判断是否可达int i,j,k=0;for(i=1;i<9

2、;i+)if(ai) for(j=0;j<i;j+) if(aj>ai) k+;return k;in t cou nt(i nt a,i nt b)/ 计算不一样的个数int i,j;for(i=j=0;i<9;i+)if(ai!=bi)j+;return j;int match(struct node m)判断是否和末状态匹配int i,j;for(i=0;i<9;i+)if(m.fi!=zzi)return 0; return 1;int comp(const void *p,const void *q) struct node *a=(struct node *

3、)p; struct node *b=(struct node *)q; if(a->c ntdif=b->c ntdif) return a->ste p-b->ste p;return a->c ntdif-b->cntdif;int visit(int x)/ 返回 hash 函数值 int i,c nt=1,sum=0; for(i=0;i<9;i+) sum+=xi*c nt+; return sum;void prin t(i nt f3)int i,j; for(i=0;i<3;i+) for(j=0;j<3;j+)prin

4、tf("%d ",fij); prin tf("n");prin tf("n");void bfs()/ 广搜int p, val,i,j,ff9,fli n=0;int head=0;int tail=0;memset(queue,0,sizeof(queue);queuehead=sour;queuehead.c ntdif=co un t(queuehead.f,zz);hashhead=visit(queuehead.f);print(queuehead.xy);/ 打印头结点while(head<=tail)struc

5、t node HH=queuehead+;int sx,sy;for(p=0;p<4;p+)flin=0;for(i=0;i<9;i+)/把头结点的值赋在此ffi=HH.fi;sx=HH.x+dir p0;sy=HH.y+dir p1;if(sx>=0&&sx<3&&sy>=0&&sy<3)ffsx*3+sy=0;ffHH.x*3+HH.y=HH.xysxsy;for(j=0;j<10000;j+)/判断是否是已经有过的状态，看hash表中是否已有 if(hashj=visit(ff)flin=1;bre

6、ak;if(fli n)con ti nue;tail+;for(i=0;i<3;i+)for(j=0;j<3;j+)queuetail.fi*3+j=queuetail.xyij=ffi*3+j;queuetail.ste p=H H.ste p+1;queuetail.x=sx;queuetail.y=sy;queuetail.c ntdif=co un t(queuetail.f,zz);hashtail=visit(queuetail.f);prin t(queuetail.xy);if(match(queuetail)printf(” 共需 %d 步！ n”,queuet

7、ail.step);return;qsort(queue+head,tail-head+1,sizeof(queue0),comp);/ 排序，每次选择 cntdif 数目最 小的扩展int mai n()int i,j,a9,b9;printf("请输入初始状态:n"); for(i=0;i<3;i+)for(j=0;j<3;j+)scan f("%d",&map ij); sour.xyij=ma p ij; sour.fi*3+j=ma pij; ai*3+j=ma pij;if(ma pij=0)sour.x=i; sour.y=j; sour.ste p=0; sour.c ntdif=0;printf("请输入终止状态：n"); for(i=0;i<3;i+)for(j=0;j<3;j+)scan f("%d",&map dest.xyij=ma pij; dest.fi*3+j=ma p ij;bi*3+j=ma pij; zzi*3+j=ma pij;prin tf("n");if(judge (a)+judge(b)