[精品]西洋棋中骑士的走法与象棋的马类似

[精品]西洋棋中骑士的走法与象棋的马类似 西洋棋中骑士的走法与象棋的马类似,只能横向二格,纵向一格或者横向一格,纵向两格(但是西洋棋棋子必须放在格子中),第1步有2种走法,第二步就有5种走法.今有5*5的棋盘,并将骑士的第一步放于左上角(0,0)的位置,试找出一个路径,使骑士在25步内把剩下的24个位置全部走完.输出结果时,将骑士的路径显示于的5*5的方格中,每一方格内显示出走到此方格内为第同步的数字. 请写出全部过程，不甚感谢～ 到处都有,给你一个,省的你找了 1 回溯法(栈回溯) #include"stdio.h" int Directions[8][2]={ {2,1},{-2,1}, {1,2},{-1,2}, {2,-1},{-2,-1}, {1,-2},{-1-2} }; int a[100],b[100],chess[5][4];/*a[100],b[100]用来记录每次跳到的X，Y，chess[5][4]代表棋盘*/ main() { int dep=1,i=0,j=0,t=0,q=1,g,s,n[100];/*dep代表跳的步数，n[100]用来记录前一次跳的方向*/ for (g=0;g<=4;g++) for(s=0;s<=3;s++) chess[g][s]=0; chess[0][0]=1;/*从(0，0)处跳*/ while(1) { while(t<=7)/*共0~7个方向，轮流试*/ { a[q]=i; b[q]=j; i=i+Directions[t][0]; j=j+Directions[t][1]; if(j>=0 &&j<=3 &&i>=0&&i<=4&&chess[i][j]==0)/*判断所跳之处是否合法*/ {q++;n[q]=t;t=0;dep++;chess[i][j] =dep; if(dep==20) goto lable;/*一旦所跳之处合法，且全局走满则可打印结果了*/ } else {t++; i=a[q];j=b[q];}/*一种方向不行，换个方向再试*/ } chess[i][j]=0;t=n[q]+1;i=a[--q];j=b[q];dep--;}/*8种方向都试完仍不行，则回溯*/ lable: for(g=0;g<=4;g++) { for(s=0;s<=3;s++) printf("%4d",chess[g][s]); printf("\n"); } } -------------------------------------------------------------------- 2 递归法 #include #define MAX_XY 6 #define true 1 #define false 0 static int anDirections[8][2]={ {2,1},{1,2}, {-1,-2},{-2,-1}, {1,-2},{-2,1}, {-1,2},{2,-1} }; typedef int status; typedef struct { int nStep; // Which step this square is int nDirection; // the 8 posibilities of direction }TSquare; TSquare Board[MAX_XY][MAX_XY]; void RecurseFind( int startX, int startY ); void RecurseFindExecute( int x, int y, int step, status &bOK ); int argc, char * argv[] ) void main( { int x,y; printf("Input X:"); scanf("%d",&x); printf("Input Y:"); scanf("%d",&y); RecurseFind( x, y ); } void RecurseFind( int startX, int startY ) { status bOK = false; int x,y; for(x=0;xMAX_XY*MAX_XY) { bOK = true; return; } int newX, newY; for(int i=0;i<8;i++) { newX = x + anDirections[i][0]; newY = y + anDirections[i][1]; if((newX>=0)&&(newX=0)&&(newY