马踏棋盘---(详细注释版)

#include<stdio.h> #include<stdlib.h> #define STACK_INIT_SIZE 100 //初始化栈的大小 #define n 10 typedef struct { int x; int y; }Coordinate;//坐标 int chessboard[8][8]={0};//初始化棋盘 Coordinate move[8]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};//坐标移动方向 用这种数据类型的好处多多 typedef struct { int ord;//接收当前所处方向 Coordinate seat;//接收当前所处位置 int di;//下一个方向 (0~7) }SElemType;//该数据类型的名字 ,棋盘信息结构体类型 typedef struct//定义栈的元素 { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的大小 }SqStack;//该数据类型的名字 int InitStack(SqStack *s1)//开辟一个栈空间,s1是指向SqStack类型的指针 { s1->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));//开辟100份SElemType大小的栈空间,并且返回 if(!s1->base) exit(1); s1->top=s1->base; s1->stacksize=STACK_INIT_SIZE; return (1); } SElemType Pop(SqStack*s,SElemType m)//位置:位置元素出栈 { m=*(--s->top); return m; } int Push(SqStack *s1,SElemType m)//位置:元素入栈 { *(s1->top++)=m; return 1; } int StackEmpty(SqStack *s)//栈:判空 返回1:栈空,,,,,返回0:栈不空 { if(s->base==s->top) return (1); else return (0); } int Pass(Coordinate s)//判断坐标是否合法 { if(chessboard[s.x][s.y]==0&&(s.x<=7)&&(s.x>=0)&&(s.y<=7)&&(s.y>=0)) return (1); else return (0); } Coordinate NextPos(Coordinate s,int i)//下一步的位置 ;返回一个坐标;参数分别为上一个点的坐标和已经走过的方向 { s.x=s.x+move[i].x; s.y=s.y+move[i].y; return(s); } void print()//打印棋盘 { int i,j=0; for(i=0;i<8;i++) { for(j=0;j<8;j++) printf("%4d",chessboard[i][j]); printf("\n"); } } void Horse(Coordinate start) { int curstep=0;//定义当前的步数 SqStack S;//定义栈元素 SElemType e;//定义当前所处位置信息 Coordinate curpos = start;//curpos用来存储要放入棋盘各格子的信息 InitStack(&S);//初始化栈 do { if(Pass(curpos))//如果位置合法 { curstep++;// curstep = 1; chessboard[curpos.x][curpos.y]=curstep;//把棋盘对应位置赋值为当前的步数 // printf("%d *",curstep); //测试数据 e.seat=curpos;// 当前位置信息 curpos有两个成员变量x,y相同的e的这个数据类型的seat成员也是Coordinate型的数据类型 e.ord=curstep;//当前步数信息 e.di=0;//当前已经探索过的方向信息 Push(&S,e);//把标记好的棋盘信息入栈 if(curstep==64) { break;//如果已经到了最后一步完成,则退出循环 } else { curpos=NextPos(curpos,e.di);//否则,探索下一步,传入当前所处棋盘位置信息, } } else//位置不合法 { if(!StackEmpty(&S))//如果栈不为空 { Pop(&S,e);//出栈 解释一下出栈的原因:由上一步探索的下一步已经无路可走了,则把上一步的信息全部出栈,由上上一步再往下继续 if(e.di==7)//如果该步已经到了最后一个可行的方向上 { chessboard[e.seat.x][e.seat.y]=0;//将这个点的痕迹抹除 } while(e.di==7&&!StackEmpty(&S))//如果上上一个点还是7位置,则继续对其进行出栈操作;//当马走到上一个点的最后一个可走方向上的时候,栈不空 { e=Pop(&S,e); if(e.di==7) chessboard[e.seat.x][e.seat.y]=0;//抹除痕迹 curstep=e.ord;//得到方向信息 } if(e.di<7)//如果探索的位置小于7则继续探索 { e.di++; Push(&S,e);//将信息入栈 curpos=NextPos(e.seat,e.di); } } } }while(!StackEmpty(&S));//栈不空则循环继续 print() ; } int main() { int i,j; Coordinate start; printf("请输入初始位置\n"); scanf("%d %d",&start.x,&start.y);//传入初始位置坐标 Horse(start);//进入函数 return 0; }