马踏棋盘 c语言版
输入马初始位置的坐标。将初始位置进栈，经过一个while循环，取出符合条件的栈顶元素。
利用函数，找出栈顶元素周围未被占用的新位置，如果有，新位置入栈；否则弹出栈顶元素。再进行判断，最后输出。

将马随机放在国际象棋的8×8棋盘某个方格中，
马按走棋规则进行移动。
要求每个方格只进入一次，走遍棋盘上全部64个方格。记录其步骤

转载的图片

#include<stdio.h>
#include<stdlib.h>#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10typedef struct //记录坐标位置
{int x;int y;
}PosType;
typedef struct //骑士跳步
{PosType seat; int di; //标记探索的下一个方向
}SElemType;
typedef struct//栈的结构体
{   SElemType *base;SElemType *top;int stacksize;
}SqStack;   int Init1[8][8] = { {0} };//此棋盘用以记录所走过的路
int Init2[8][8] = {  {2,3,4,4,4,4,3,2},//初始化棋盘，并标记每个位置所能跳的方向{3,4,6,6,6,6,4,3},//例如当为2时，表示下一步只有两个方向可跳{4,6,8,8,8,8,6,4},//此棋盘用以记录跳棋步骤{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2},};
int HTry1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};//跳马的下一步的x位置
int HTry2[8] = {1, 2, 2, 1, -1, -2, -2, -1};//跳马的下一步的y位置void MarkPrint(PosType pos);//此路不能通过，仍标记为0
PosType NextPos(PosType curpos,int x);//按顺时针寻找下一个方向
void FootPrint(PosType &curpos,int surstep);//此路能过标记相应的步数
int Pass(PosType &curpos);//判断此路是否能通过
int InitStack(SqStack &S);//初始化栈
void DestroyStack(SqStack &S);//销毁栈
int StackEmpty(SqStack &S);//判断栈是否为空
int Push(SqStack &S,SElemType e);//入栈
int Pop(SqStack &S,SElemType &e);//出栈
void print(int curstep);//打印路线int main()
{SqStack S;                                      //栈的结构体SElemType e;                                    //标记探索的下一个方向PosType Mincurpos,curpos,start;                 //记录坐标位置int curstep;                                    //记录步数InitStack(S);                                   //初始化栈printf("请输入起始位置");scanf("%d%d",&start.x,&start.y);                //请输入起始位置curpos = start;                                 //记录初始坐标位置curstep = 1;                                    //记录坐标顺序位置do{if(Pass(curpos)) {              //判断此路是否能通过FootPrint(curpos,curstep);  //此路能过标记相应的步数e.di = 0;                   //标记探索的下一个方向e.seat= curpos;             //记录坐标位置Push(S,e);                  //入栈if(curstep == 64) {         //判断栈满print(curstep);         //打印路线DestroyStack(S);        //销毁栈return 1;}curpos = NextPos(curpos,e.di);  //按顺时针寻找下一个方向curstep ++;                     //步数加一}else {if(!StackEmpty(S)) {                //判断栈不为为空Pop(S,e);                       //退栈curstep --;                     //步数减一while(e.di == 7 && !StackEmpty(S)) {MarkPrint(e.seat);          //此路不能通过，仍标记为0Pop(S,e);                   //退栈curstep --;                 //步数减一}if(e.di < 7) {Mincurpos = curpos;             //Mincurpos记录上次位置e.di ++;                        //方向加一curpos = NextPos(e.seat,e.di);  //按顺时针寻找下一个方向while(Mincurpos.x == curpos.x && Mincurpos.y == curpos.y && e.di < 7) {e.di ++;                        //判断此位置的下一个位置的八个方向的最小值是否相同，若相同则直接跳过curpos = NextPos(e.seat,e.di);  //按顺时针寻找下一个方向}Push(S,e);                          //出栈curstep ++;                         //步数加一}}}}while(!StackEmpty(S));                             //栈不为空DestroyStack(S);                                    //销毁栈return 0;
}void print(int curstep)                                 //打印路线
{for(int i = 0; i < 8; i++)  {for(int j = 0; j < 8; j++) printf("%3d",Init1[i][j]);              //打印路线printf("\n");}printf("\n");printf("\n");getchar();
}void MarkPrint(PosType pos)                             //此路不能通过，仍标记为0
{Init1[pos.x][pos.y] = 0;
}PosType NextPos(PosType curpos,int x)                   //寻找下一个位置Init2[8][8]中最小的位置，并且此路没有走过
{ //寻找下一个位置Init2[8][8]中最小的位置，并且此路没有走过PosType MinCurpos,temp;MinCurpos.x = -1;MinCurpos.y = -1;//置此为最小的方向for(;x < 8; x++) {temp.x = curpos.x + HTry1[x];                   //跳马的下一步的x位置temp.y = curpos.y + HTry2[x];                   //跳马的下一步的y位置if(temp.x < 0 || temp.x > 7 || temp.y < 0 || temp.y > 7 || Init1[temp.x][temp.y]) continue;//保证此位置在棋盘中if(MinCurpos.x == -1 && MinCurpos.y == -1)      //先找到下个位置第一个合法的位置 MinCurpos = temp;else if( Init2[MinCurpos.x][MinCurpos.y] > Init2[ temp.x][temp.y] )//比较找最小MinCurpos= temp;}if(MinCurpos.x == -1 && MinCurpos.y == -1)          //如果没有下个位置，返回原来位置return curpos;return MinCurpos;                                   //如果有下个位置，返回位置
}void FootPrint(PosType &curpos,int curstep)             //此路能过标记相应的步数
{Init1[curpos.x][curpos.y] = curstep;                //此路能过标记相应的步数,将Init1存入步数
}int Pass(PosType &curpos)                               //判断此路是否能通过
{if(!Init1[curpos.x][curpos.y])                      //此路不能通过，return 1，否则返回 0return 1;else return 0;
}void DestroyStack(SqStack &S)                           //销毁栈
{S.base = S.top;                                     //base=topS.stacksize = 0;                                    //size置为0
}int StackEmpty(SqStack &S)                              //判断栈满
{if(S.base == S.top)                                 return 1;else return 0;
}int InitStack(SqStack &S)                               //初始化栈
{   S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));//将s.base申请跳步类型100个空间if(!S.base) return 0;                               S.top = S.base;S.stacksize = STACK_INIT_SIZE;                      //长度给100return 1;
}int Push(SqStack &S,SElemType e)                        //入栈
{if(S.top - S.base >= S.stacksize ) {                //顶减底等于现在的栈中元素个数S.base = (SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT )*sizeof(SElemType));//对malloc申请的内存进行大小的调整.调整为110   if(!S.base) return 0;S.top = S.base +S.stacksize;                    //顶为底加长度S.stacksize += STACKINCREMENT;                  //长度加10}*S.top++ = e;return 1;
}int Pop(SqStack &S,SElemType &e)                        //出栈    
{   if(S.top == S.base) return 0;e = *--S.top;                                       //e=*--S.topreturn 1;
}

https://xuptacm.github.io/