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

这篇文章主要介绍如何使用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 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++基于栈的深搜算法实现马踏棋盘”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注编程网其他教程频道！