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

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

(0)

相关推荐

  • C/C++实现马踏棋盘算法

    本文实例为大家分享了C/C++实现马踏棋盘的具体代码,供大家参考,具体内容如下 问题描述:将马随机放在国际象棋的8×8棋盘Board[0-7][0-7]的某个方格中,马按走棋规则进行移动.要求每个方格只进入一次,走遍棋盘上全部64个方格. 问题求解算法简述: 1.深度优先遍历+回溯法 2.贪心算法+深度优先遍历+回溯法 解法1描述: 1.使用一个二维数组Step[8][8]= {-1}来表示棋盘,起跳位置做为当前位置Step[i][j],设置NumOfSteps = 0: 2.设置当前位置Ste

  • C++贪心算法实现马踏棋盘

    本文实例为大家分享了C++贪心算法实现马踏棋盘的具体代码,供大家参考,具体内容如下 算法实现流程: 步骤1:初始化马的位置(结构体horse {x, y}) 步骤2:确定马从当前点出发,可跳跃的附近8个点,以结构体Jump数组给出,但需判断当前给出的附近8个点是否曾经访问过,或者是否这8个点超出棋盘尺寸. 步骤3:跟据步骤2确定跳跃的点,分别计算可跳跃点的下下一步,可跳跃点的个数.并选出下下步可跳跃点数最少的点作为马下一步跳跃的点.(举例说明:马当前所在点坐标(4,4),下一步可跳跃点有(5,2

  • C++实现骑士走棋盘算法

    本文实例为大家分享了C++实现骑士走棋盘算法的具体代码,供大家参考,具体内容如下 1.问题描述 骑士旅游Knight tour在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出已不可考,骑士的走法为西洋 棋的走法,骑士可以由任一个位置出发,它要如何走完所有的位置. 2.基本思路 骑士的走法,基本上可以用递回来解决,但是纯粹的递回在维度大时相当没有效率,一个聪明的解法由J.CWarnsdorff 在1823年提出, 简单地说,先将最难的位置走完,接下来的路就宽广了,骑士所想要的下一步,为下一不

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

    马踏棋盘(基于栈的深搜算法实现) 简单来说,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径,这就是马踏棋盘的简单描述. 话不多说,代码如下,要是有什么不懂的地方,欢迎讨论~ #include <stdio.h> #include <stdlib.h> #define M 8 //行 #define N 8 //列   typedef struct snode    //坐标 {     int flag;     int x;     int y; }sta

  • Python基于回溯法子集树模板解决马踏棋盘问题示例

    本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题.分享给大家供大家参考,具体如下: 问题 将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案. 分析 说明:这个图是5*5的棋盘. 类似于迷宫问题,只不过此问题的解长度固定为64 每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择. 走到一

  • java数据结构和算法之马踏棋盘算法

    本文实例为大家分享了java实现算法之马踏棋盘的具体代码,供大家参考,具体内容如下 一.马踏棋盘算法介绍 马踏棋盘算法也被称为骑士周游问题将马随机放在国际象棋的8×8棋盘Board[0-7][0-7]的某个方格中,马按走棋规则(马走日字)进行移动.要求每个方格只进入一次,走遍棋盘上全部64个方格 二.骑士周游问题的思路分析 1.创建棋盘 chessBoard , 是一个二维数组2.将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList), 最多

  • java数据结构与算法之马踏棋盘

    本文实例为大家分享了java数据结构与算法之马踏棋盘的具体代码,供大家参考,具体内容如下 马踏棋盘算法也被称为骑士周游问题 将马随机放在过期象棋的8x8棋盘的某个方格中,马按走棋规则进行移动,要求每个方格只进入一次,走遍棋盘上全部64个方格 骑士周游问题结局步骤和思路 1.创建棋盘chessBoard,是一个二维数组2.将当前位置设置为已个访问,然后根据当前位置,计算马儿还能走那些位置,并放到一个集合中(ArrayList),最多8个位置3.变量ArrayList存放的所有位置,看看哪个可以走通

  • C++算法设计之马踏棋盘的实现

    本文实例为大家分享了C++算法设计之马踏棋盘的具体代码,供大家参考,具体内容如下 (一)马踏棋盘经典算法描述: (1)马踏棋盘是经典的程序设计问题之一,主要的解决方案有两种:一种是基于深度优先搜索的方法,另一种是基于贪婪算法的方法.第一种基于深度优先搜索的方法是比较常用的算法,深度优先搜索算法也是数据结构中的经典算法之一,主要是采用递归的思想,一级一级的寻找,遍历出所有的结果,最后找到合适的解.而基于贪婪的算法则是制定贪心准则,一旦设定不能修改,他只关心局部最优解,但不一定能得到最优解. [问题

  • Java实现马踏棋盘算法

    本文实例为大家分享了Java实现马踏棋盘的具体代码,供大家参考,具体内容如下 马在某个点最多可能有8种走法,用递归和回溯实现. 注:代码中,查找下一个可走坐标是从右下第一个开始的,也就是图中的4.可以通过修改a,b...h的值来改变顺序. 代码: /**  * 马踏棋盘算法   * 递归和回溯  *  */ public class HorseStep {          public static int X = 8;     public static int Y = 8;        

  • java实现马踏棋盘的算法

    本文实例为大家分享了java实现马踏棋盘的具体代码,供大家参考,具体内容如下 马踏棋盘算法介绍 8X8棋盘,马走日字,要求每个方格只进入一次,走遍棋盘上全部64个方格. 代码: public class HorseChessBoard {     private static int X;//棋盘的列数     private static int Y;//棋盘的行数     //创建一个数组,标记棋盘的各个位置是否被访问过     private static boolean visited[

  • java学习笔记之马踏棋盘算法

    马踏棋盘或骑士周游问题 1.马踏棋盘算法也被称为骑士周游问题2.将马随机放在国际象棋的 8×8 棋盘 Board[0-7][0-7]的某个方格中,马按走棋规则(马走日字)进行移动.要求每个方格只进入一次,走遍棋盘上全部 64 个方格 思路 会使用到深度优先思想和类似迷宫问题的寻路策略问题,和八皇后问题也有相似. 1.用一个二维数组建立整张棋盘.用另外一个二维数组保存棋盘的每一个位置是否走过2.马在棋盘上有一个初始位置,将这个位置设为已走过,并将步数设为1.3.获得在这个位置上,马下一步能走的位置

随机推荐