棋盘跳马问题
暑假训练张老师讲的,递归问题。
在一个5*5的棋盘上,马从某个格子出发,只能跳到能和现在所站位置成日子型的格子中,找到能跳完这25个格子的所有方式。
举例:
|
X1,y1 |
|
X1,y1 |
|
X1,y1 |
|
|
|
X1,y1 |
|
|
x,y |
|
|
X1,y1 |
|
|
|
X1,y1 |
|
X1,y1 |
|
X1,y1 |
|
这里不如就好好接受老师的思路,自己的太不顺了。
#include <stdio.h> int a[9][9]={0}; void prt(){ int i,j; for(i=2;i<=6;i++){ for(j=2;j<=6;j++) printf("%3d",a[i][j]); printf("\n"); } printf("\n\n"); } void jump(int x,int y,int k){ int i,x1,y1; for(i=1;i<=8;i++){ /*显而易见是对应的可以跳到的8个位置。*/ switch(i){ case 1:x1=x-1;y1=y+2; break; case 2:x1=x+1;y1=y+2; break; case 3:x1=x+2;y1=y+1; break; case 4:x1=x+2;y1=y-1; break; case 5:x1=x+1;y1=y-2; break; case 6:x1=x-1;y1=y-2; break; case 7:x1=x-2;y1=y-1; break; case 8:x1=x-2;y1=y+1; break; } if(a[x1][y1]==0){ a[x1][y1]=k; /*其实这句话我觉得很不顺,可再也想不到更好的表达,*/ if(k==25) /*这样是为了打印的时候在期盼的对应格子打印出每一步跳的痕迹。*/ prt(); else jump(x1,y1,k+1); a[x1][y1]=0; } } } void main(){ int i,j; for(i=0;i<2;i++){ /*话说好佩服张老师这样开数组,开成一个9*9的数组,*/ for(j=0;j<9;j++){ /*然后把最上下左右两行标记为不存在,这样就免去了判断是不是跳出界的麻烦。*/ a[i][j]=-1; a[j][i]=-1; } } for(i=7;i<9;i++){ for(j=0;j<9;j++){ a[i][j]=-1; a[j][i]=-1; } } a[2][2]=1; /*自己写的时候还妄想能打印出所有情况,*/ jump(2,2,2); /*只是以第一行第一列这一格为起点情况就这么多了。*/ } /*老师还说可以自己加一个变量标记一下出现的情况的具体数目。*/