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;
    }
}

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