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

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

这篇文章主要介绍如何使用C++基于栈的深搜算法实现马踏棋盘，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

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

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

#include<stdio.h>#include<stdlib.h>#defineM8//行#defineN8//列typedefstructsnode//坐标{intflag;intx;inty;}stack;typedefstructnode{inttop;//记录走了多少步top+1intflag;//记录上一步走的方向stack*p;//路径栈}LNode;LNode*CreateStacke();//创建，并初始化voidJudge(LNode*s,intchess[][N]);//判断往哪走voidPush(LNode*s,stackx);//入栈操作voidPop(LNode*s);//出栈操作intIsFull(LNode*s);//判满intIsEmpty(LNode*s);//判空intmain(){intchess[M][N]={0};//棋盘inti,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");}return0;}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放在栈底returns;}voidJudge(LNode*s,intchess[][N]){intch[8][2]={//马可能走的八个方向{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};inti,j=1,flag=1;stackt;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;}}}voidPush(LNode*s,stackx){if(IsFull(s)){printf("栈上溢，不能进行入栈操作!\n");exit(0);}else{s->top++;s->p[s->top]=x;}}voidPop(LNode*s){if(IsEmpty(s)){printf("栈为空，不能进行出栈操作!\n");exit(0);}s->top--;}intIsFull(LNode*s){if(s->top>=M*N){return1;}else{return0;}}intIsEmpty(LNode*s){if(s->top==-1){return1;}else{return0;}}

以上是“如何使用C++基于栈的深搜算法实现马踏棋盘”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注恰卡编程网行业资讯频道！