马踏棋盘(基于栈的深搜算法实现)
简单来说,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径,这就是马踏棋盘的简单描述。
话不多说,代码如下,要是有什么不懂的地方,欢迎讨论~
#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; } }
以上就是c/c++开发分享C++基于栈的深搜算法实现马踏棋盘的全部内容,希望对大家的学习有所帮助,也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。
需要了解更多c/c++开发分享C++基于栈的深搜算法实现马踏棋盘,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1058772.html