骑士周游世界之快速周游

《骑士周游世界之快速周游》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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&&i

6、[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;i

7、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(top

8、  for(t=temp;t<8;t++,temp1++){    /*Howmanywaysforthehorsecanjumpforfirsttime*/  ti+=row[