一个用C++编写的马踏棋盘递归算法源程序

#include "stdio.h"
#include "malloc.h"
#define M 8
#define N 8

typedef struct{
int r,c;
}PosType;

int board[M][N];/*棋盘数组*/
int htry1[]={-2,-1,1,2,2,1,-1,-2};/*当前位置的8个下一个可能位置*/
int htry2[]={1,2,2,1,-1,-2,-2,-1};
int sum=0;

void InitBoard(){/*棋盘数组初始化*/
for(int i=0;ifor(int j=0;j{board[i][j]=0;}
}

int Pass(PosType curpos){/*判断当前位置是否可行*/
int i,j;
i = curpos.r;
j = curpos.c;
if(board[i][j]>0||i<0||j<0||i>=M||j>=N) return 0;
else return 1;
}

void FootPrint(PosType curpos,int step){/*当前位置留下脚印*/
int i,j;
i = curpos.r;
j = curpos.c;
board[i][j] = step;
}

void FreePrint(PosType curpos){/*擦除当前位置留下的脚印*/
int i,j;
i = curpos.r;
j = curpos.c;
board[i][j] = 0;
}

PosType NextPos(PosType curpos,int di){
/*根据当前位置和搜索方向，得到下一个位置*/
curpos.c+=htry1[di];
curpos.r+=htry2[di];
return curpos;
}

void PrintBoard(){
for(int i=0;iprintf("\n");
for(int j=0;jprintf("%4d",board[i][j]);
}
}

void HorseChess(int curstep,PosType curpos){
int j;
PosType curposnext;

if(curstep==1)FootPrint(curpos,1);
if(curstep==64){
sum++;
printf("sum=%4d",sum);
PrintBoard();
printf("\n");
}
else for(j=0;j<8;++j){
curposnext = NextPos(curpos,j);/*下一个位置*/
if(Pass(curposnext)){
FootPrint(curposnext,curstep+1);/*当前位置留下脚印*/
HorseChess(curstep+1,curposnext);
}
}
FreePrint(curpos);
}

void main(){
int i,j;
PosType start;
InitBoard();
printf("\nPlease input i and j:");
scanf("%d%d",&i,&j);
if(!(i<0 || j<0 || i>=M || j>=N)){
start.r = i;
start.c = j;
HorseChess(1,start);
}
}