马踏棋盘（基于栈的深搜算法实现）
简单来说，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径，这就是马踏棋盘的简单描述。
话不多说，代码如下，要是有什么不懂的地方，欢迎讨论~
#include <stdio.h>
#include <stdlib.h>
#define M 8 //行
#define N 8 //列
typedef struct snode //坐标
{
int flag;
int x;
int y;
}stack;
typedef struct node
{
int top; //记录走了多少步top+1
int flag; //记录上一步走的方向
stack * p; //路径栈
}LNode;
LNode * CreateStacke(); //创建，并初始化
void Judge(LNode * s, int chess[][N]); //判断往哪走
void Push(LNode * s, stack x); //入栈操作
void Pop(LNode * s); //出栈操作
int IsFull(LNode * s); //判满
int IsEmpty(LNode * s); //判空
int main()
{
int chess[M][N] = {0}; //棋盘
int i, j; //循环变量
LNode * step; //step存的是走的路径
step = CreateStacke();
Judge(step, chess);
for (i = 0; i < N; i++){
for (j = 0; j < M; j++){
printf("%2d ", chess[i][j]);
}
printf("\n");
}
return 0;
}
LNode * CreateStacke()
{
LNode * s = (LNode *)malloc(sizeof(LNode));
if (!s){
printf("内存空间不足!\n");
system("pause");
exit(0);
}
s->p = (stack *)malloc(sizeof(stack) * M * N);
if (!s->p){
printf("内存空间不足!\n");
system("pause");
exit(0);
}
s->top = -1; // 把top放在栈底
return s;
}
void Judge(LNode * s, int chess[][N])
{
int ch[8][2] = { //马可能走的八个方向
{1, -2}, { 2, -1},
{2, 1 }, { 1, 2 },
{-1, 2}, {-2, 1 },
{-2, -1},{-1, -2}
};
int i, j = 1, flag = 1;
stack t;
printf("请输入马的初始位置：(%d * %d)\n", M, N);
scanf("%d%d", &t.y, &t.x);
if (t.x <= 0 || t.x > N || t.y <= 0 || t.y > N){
printf("输入的坐标超出范围！\n");
exit(0);
}
t.x--;
t.y--;
chess[t.y][t.x] = 1; //选择马的第一个落脚点
Push(s, t);
while (s->top < M * N - 1 && s->top != -1){
for (i = 0; i < 8; i++){
t.x = s->p[s->top].x + ch[i][0];
t.y = s->p[s->top].y + ch[i][1];
//如果它的坐标没有超出范围，并且没有走过，则把该路线存入路径栈
if (t.x >= 0 && t.y >= 0 && t.x < N && t.y < M && !chess[t.y][t.x]){
if(flag){ //没有退回去
Push(s, t);
chess[t.y][t.x] = s->top + 1;
s->p[s->top - 1].flag = i;
flag = 1;
break;
}
else{ //退回去了
if (s->p[s->top].flag < i){ //重新走时，让它的方向不等于原先的方向
flag = 1;
}
}
}
}
//如果没有能走的路时，即，所有的路径都超出范围，或者，该位置已经走过了，则，退到上一步，重新选择；
if (i == 8){
chess[s->p[s->top].y][s->p[s->top].x] = 0;
Pop(s);
flag = 0;
}
}
}
void Push(LNode * s, stack x)
{
if (IsFull(s)){
printf("栈上溢，不能进行入栈操作!\n");
exit (0);
}
else{
s->top++;
s->p[s->top] = x;
}
}
void Pop(LNode * s)
{
if (IsEmpty(s)){
printf("栈为空，不能进行出栈操作!\n");
exit(0);
}
s->top--;
}
int IsFull(LNode * s)
{
if (s->top >= M * N){
return 1;
}
else{
return 0;
}
}
int IsEmpty(LNode * s)
{
if (s->top == -1){
return 1;
}
else{
return 0;
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
