资源描述:
《骑士周游世界之快速周游》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、骑士周游世界之快速周游(小于1秒)**走一步看两步**【问题分析】(1) 棋盘的表示方法我们可以用一个8×8的二维数组A(I,J)来表示国际象棋的棋盘,在马还没有开始周游棋盘时,棋盘上所有的格都置为零。以后,马跳到哪个格,就将马跳跃的步数记录在相应的空格里。(2) 马的跳跃方向的确定在国际象棋的棋盘上,一匹马共有八个可能的跳跃方向。我们设置一组坐标增量来描述这八个条约方向:①(1,2) ②(2,1)③(2,-1) ④(1,-2)⑤(-1,-2) ⑥(-2,-1)⑦(-2,1) ⑧(-1,2)(3)马的跳跃方向的表示设
2、I表示行,J表示列,行增量为DI(R),列增量为DJ(R),则马向某个方向试探性地跳跃一步之后的新坐标应该表示为:NI=I+DI(R),NJ=J+DJ(R)。(4)朝某个方向试探性地跳跃一步再看下一步(取下一步最小可走方向(处里边角问题)),任何一点的坐标加上要试探方向的坐标增量之后,都要判断一下是否已经超出了棋盘的边界。即:当I<0,或I>8,或J<0,或J>8时,都表示已经超出了棋盘的边界,这时,应该放弃该方向,转向试探下一个方向,在不出界的情况下,如果A(NI,NJ)=0,则表示该方向的前方有通路,可以继续向前跳跃。如果A(NI,NJ
3、)>0,则表示该格已经走过了,不能再走。放弃该方向,并转向下一个方向进行试探。#include"stdio.h"#include"conio.h"#defineN19 /*Howmanythehorse最好不要超过19(超出屏幕)*/inttop=0;structstack{ intx;inty;intstep;}ma[N*N+1]={{0,0,0}};voidpush(inta[][N],inti,intj,intm){ ma[top].x=i;ma[top].y=j;ma[top].step=m;a[j]=++top;}int
4、pop(inta[][N]){ inttemp;top--;a[ma[top].x][ma[top].y]=0;ma[top].x=0;ma[top].y=0;temp=ma[top].step+1;ma[top].step=0;returntemp;}intjump(inti,intj,inta[][8]){ intcol[]={2,1,-1,-2,-2,-1,1,2};introw[]={-1,-2,-2,-1,1,2,2,1};intt,ti=i,tj=j,count=0;for(t=0;t<8;t++){ ti+=ro
5、w[t];tj+=col[t]; if(judge(ti,tj,a)) count++; /*Howmanywaysforthehorsecanjumpforsecondtime.*/ ti-=row[t];tj-=col[t];}returncount;}intjudge(inti,intj,inta[][N]) /*Judgethepositioncanjump*/{ if(i>=0&&j>=0&&i6、[8],intb[8]){ inti,min=a[0],t=0;for(i=1;i<8;i++){ if(min>a&&a>-1&&a<8){ min=a; /*FindtheMin-waythehorsetojump*/ t=b; }}returnt;}voiddisp(inta[][N]){ inti,j;for(i=0;i7、ty){ inti=x,j=y,min,ti,tj,t,temp=0,flag=0,temp1=0;intcount[8],num[8]={0};intcol[]={2,1,-1,-2,-2,-1,1,2};introw[]={-1,-2,-2,-1,1,2,2,1};inta[N][N]={{0}};for(x=0;x<8;x++) count[x]=8;push(a,i,j,0);while(top8、 for(t=temp;t<8;t++,temp1++){ /*Howmanywaysforthehorsecanjumpforfirsttime*/ ti+=row[