骑士周游世界之快速周游.doc

骑士周游世界之快速周游（小于1秒）*走一步看两步*【问题分析】(1)棋盘的表示方法我们可以用一个88的二维数组A(I，J)来表示国际象棋的棋盘，在马还没有开始周游棋盘时，棋盘上所有的格都置为零。以后，马跳到哪个格，就将马跳跃的步数记录在相应的空格里。(2)马的跳跃方向的确定在国际象棋的棋盘上，一匹马共有八个可能的跳跃方向。我们设置一组坐标增量来描述这八个条约方向： （1，2） （2，1） （2，-1） （1，-2） （-1，-2） （-2，-1） （-2，1） （-1，2）(3) 马的跳跃方向的表示设I表示行，J表示列，行增量为DI（R），列增量为DJ（R），则马向某个方向试探性地跳跃一步之后的新坐标应该表示为：NI=I+DI（R），NJ=J+DJ（R）。(4) 朝某个方向试探性地跳跃一步再看下一步（取下一步最小可走方向（处里边角问题），任何一点的坐标加上要试探方向的坐标增量之后，都要判断一下是否已经超出了棋盘的边界。即：当I 8，或J 8时，都表示已经超出了棋盘的边界，这时，应该放弃该方向，转向试探下一个方向，在不出界的情况下，如果A（NI，NJ）=0，则表示该方向的前方有通路，可以继续向前跳跃。如果A（NI，NJ）0，则表示该格已经走过了，不能再走。放弃该方向，并转向下一个方向进行试探。#includestdio.h#includeconio.h#define N 19 /*How many the horse最好不要超过19（超出屏幕）*/int top=0;struct stack int x;int y;int step;maN*N+1=0,0,0;void push(int aN,int i,int j,int m) matop.x=i;matop.y=j;matop.step=m;aj=+top;int pop(int aN) int temp;top-;amatop.xmatop.y=0;matop.x=0;matop.y=0;temp=matop.step+1;matop.step=0;return temp;int jump(int i,int j,int a8) int col=2,1,-1,-2,-2,-1,1,2;int row=-1,-2,-2,-1,1,2,2,1;int t,ti=i,tj=j,count=0;for(t=0;t=0&j=0&iN&jN&aj=0)return 1;return 0;sort(int a8,int b8) int i,min=a0,t=0;for(i=1;ia&a-1&a8) min=a; /*Find the Min-way the horse to jump*/ t=b;return t;void disp(int aN) int i,j;for(i=0;iN;i+) for(j=0;jN;j+)printf(%4d,aj); printf(n);void horse(int x,int y) int i=x,j=y,min,ti,tj,t,temp=0,flag=0,temp1=0;int count8,num8=0;int col=2,1,-1,-2,-2,-1,1,2;int row=-1,-2,-2,-1,1,2,2,1;int aNN=0;for(x=0;x8;x+) countx=8;push(a,i,j,0);while(topN*N) ti=i;tj=j;temp1=0;flag=0;for(x=0;x8;x+) countx=8;for(t=temp;t8;t+,temp1+) /*How many ways for the horse can jump for first time*/ ti+=rowt;tj+=colt; if(judge(ti,tj,a) counttemp1=jump(ti,tj,a); numtemp1=t; flag=1; ti-=rowt;tj-=colt;if(flag) min=sort(count,num); ti+=rowmin;tj+=colmin; push(a,ti,tj,min); /*In the stack*/ i=ti;j=tj