C++基于栈的深搜算法实现马踏棋盘

马踏棋盘（基于栈的深搜算法实现）

简单来说，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径，这就是马踏棋盘的简单描述。

话不多说，代码如下，要是有什么不懂的地方，欢迎讨论~

#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 impty(lnode * s); //判空int main(){ int chess[m][n] = {0};  //棋盘 int i, j; //循环变量 lnode * step;     //step存的是走的路径  step = createsta警官学院cke();  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("pau");  exit(0); } s->p = (stack *)malloc(sizeof(stack) * m * n); if (!s->p){  printf("内存空间不足!\n");  system("pau");  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}, 2016年9月28日{-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-&g掉了张惠妹t;p[s->top - 1].flag = i;     flag = 1;     break;    }    el{    //退回去了     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); } el{  s->top++;  s->p[s->top] = x;   }}void pop(lnode * s){ if (impty(s)){  printf("栈为空，不能进行出栈操作!\n");  exit(0); } s->top--;}int isfull(lnode * s){ if (s->top >= m * n){  return 1; } el{  return 0; }}i营业税改征增值税nt impty(lnode * s){ if (s->top == -1){  return 1; } el{  return 0; }}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持www.887551.com。