八数码c语言代码.doc

《八数码c语言代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八数码c语言代码#include#include#includestructnode{intx,y;intcntdif;intstep;intf[9];intxy[3][3];}queue[10000];intmap[3][3];intdir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};inthash[10000];intzz[9];intf1,f2;structnodesour,dest;intjudge(inta[])//用逆序数判断是否可达

2、{inti,j,k=0;for(i=1;i<9;i++)if(a[i])for(j=0;ja[i])k++;returnk;}intcount(inta[],intb[])//计算不一样的个数{inti,j;for(i=j=0;i<9;i++)if(a[i]!=b[i])j++;returnj;}intmatch(structnodem)//判断是否和末状态匹配{inti,j;for(i=0;i<9;i++)if(m.f[i]!=zz[i])return0;return1;}intcomp(con

3、stvoid*p,constvoid*q){structnode*a=(structnode*)p;structnode*b=(structnode*)q;if(a->cntdif==b->cntdif)returna->step-b->step;returna->cntdif-b->cntdif;}intvisit(intx[])//返回hash函数值{inti,cnt=1,sum=0;for(i=0;i<9;i++)sum+=x[i]*cnt++;returnsum;}voidprint(intf[][3]){inti,j

4、;for(i=0;i<3;i++){for(j=0;j<3;j++)printf("%d",f[i][j]);printf("");}printf("");}voidbfs()//广搜{intp,val,i,j,ff[9],flin=0;inthead=0;inttail=0;memset(queue,0,sizeof(queue));queue[head]=sour;queue[head].cntdif=count(queue[head].f,zz);hash[head]=visit(queue[head].f);p

5、rint(queue[head].xy);//打印头结点while(head<=tail){structnodeHH=queue[head++];intsx,sy;for(p=0;p<4;p++){flin=0;for(i=0;i<9;i++)//把头结点的值赋在此ff[i]=HH.f[i];sx=HH.x+dir[p][0];sy=HH.y+dir[p][1];if(sx>=0&&sx<3&&sy>=0&&sy<3){ff[sx*3+sy]=0;ff[HH.x*3+HH.y]=HH.xy[sx][sy];for(j=0;j<

6、10000;j++)//判断是否是已经有过的状态,看hash表中是否已有{if(hash[j]==visit(ff)){flin=1;break;}}if(flin)continue;tail++;for(i=0;i<3;i++)for(j=0;j<3;j++)queue[tail].f[i*3+j]=queue[tail].xy[i][j]=ff[i*3+j];queue[tail].step=HH.step+1;queue[tail].x=sx;queue[tail].y=sy;queue[tail].cntdif=cou

7、nt(queue[tail].f,zz);hash[tail]=visit(queue[tail].f);print(queue[tail].xy);if(match(queue[tail])){printf("共需%d步！",queue[tail].step);return;}}}qsort(queue+head,tail-head+1,sizeof(queue[0]),comp);//排序，每次选择cntdif数目最小的扩展}}intmain(){inti,j,a[9],b[9];printf("请输入初始状态:"

8、);for(i=0;i<3;i++)for(j=0;j<3;j++){scanf("%d",&map[i][j]);sour.xy[i][j]=map[i][j];sour.f[i*3+j]=map[i][j];a[i*3+j]=map[i][j];if(map[i][j]=