本文主要是介绍深度优先遍历解决迷宫问题(顺序栈的应用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
学习贺利坚老师课程
数据结构例程——迷宫问题（用栈结构）_数据结构迷宫问题-CSDN博客文章浏览阅读3.1w次，点赞25次，收藏118次。本文针对数据结构基础系列网络课程(3)：栈和队列中第6课时栈的应用2-迷宫问题。例：求出从入口到出口的路径 程序实现：#include #define MaxSize 100#define M 8#define N 8int mg[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1},_数据结构迷宫问题https://blog.csdn.net/sxhelijian/article/details/48465369本人详细解析博客
迷宫问题构思_概要设计 迷宫问题-CSDN博客文章浏览阅读1.4k次，点赞6次，收藏4次。背景:交通运输是支撑国民经济发展的重要产业，承担着促进商品的高效快捷流转的使命，物流行业在现代社会发展中有着十分积极的作用，在新的时代背景下物流业需要更加智能化的管理与服务模式。“智慧物流”起源于IBM提出的“智慧地球”这一概念，经过我国政府“感知中国”、“互联网+物流”建设战略，智慧物流迅速崛起。智慧物流可以深入推动供应链整合升级，促进物流行业创新发展与结构调整，为物流行业在影响社会生产与物资流通的同时，转变产业发展方式以满足客户的需求，促进产品流通。_概要设计 迷宫问题https://blog.csdn.net/qq_57484399/article/details/127308349版本更新日志
v1.0 : 重构命名语句, 让代码易读, 地图可视化显示, 方便玩家观看
main里面的子函数与结构:
节点方向结构
typedef struct
{int x;int y;int direction;
}Map_Node; //节点方向结构路线栈
typedef struct
{Map_Node data[MaxSize];int top;
}Route_stack; //路线栈深度有限遍历寻路, 并记录路线的子函数
bool Find_path(int start_pointX,int start_pointY,int export_pointX,int export_pointY);主函数调用
int main()
{int start_pointX;int start_pointY;int export_pointX;int export_pointY;bool result;for(int display_x = 1; display_x < X+1;display_x++){if(display_x == 1){printf(" →Y");printf("\t");for(int display_y = 1; display_y < Y+1;display_y++){printf("%d ",display_y);}printf("\n");printf("↓ X");printf("\n");}printf(" %d ",display_x);printf("\t");for(int display_y = 1; display_y < Y+1;display_y++){printf("%d ",mapper[display_x][display_y]);}printf("\n");}printf("\n请输入初始地址:\n(例如:1,1)");scanf("%d, %d", &start_pointX, &start_pointY);printf("\n请输入出口地址:\n(例如:8,8)");scanf("%d, %d", &export_pointX, &export_pointY);result = Find_path(start_pointX,start_pointY,export_pointX,export_pointY);if(result == 1){printf("此路有解!");}elseif(result == 0){printf("此路无解!");}return 0;
}
main.cpp 源代码
#include <stdio.h>#define MaxSize 100
#define X 8
#define Y 8//地图坐标
int mapper[X+2][Y+2] =
{{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,0,1,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}
};typedef struct
{int x;int y;int direction;
}Map_Node; //节点方向结构typedef struct
{Map_Node data[MaxSize];int top;
}Route_stack; //路线栈bool Find_path(int start_pointX,int start_pointY,int export_pointX,int export_pointY)
{//当探索前节点的x,y,当前节点的方向,是否已经找到int find_X,find_Y,find_direction,already_find;//定义计数变量int counter;//初始化路线栈Route_stack depth_route;//初始化栈顶指针depth_route.top = -1;//开始寻路(路线栈加入起点)depth_route.top++;depth_route.data[depth_route.top].x = start_pointX;depth_route.data[depth_route.top].y = start_pointY;//路线栈节点方向标明depth_route.data[depth_route.top].direction = -1; //起点未标明方向//路线栈加入节点即被激活while(depth_route.top > -1){//当前路线到达的节点find_X = depth_route.data[depth_route.top].x;find_Y = depth_route.data[depth_route.top].y;find_direction = depth_route.data[depth_route.top].direction;//判断当前节点是否到达终点if(find_X == export_pointX && find_Y == export_pointY){//从栈底到栈顶,输出当前路线for(counter = 0; counter <= depth_route.top; counter++){printf("\t(%d,%d)",depth_route.data[counter].x,depth_route.data[counter].y);if((counter+1)%5 == 0){printf("\n");}}printf("\n");return 1;}//如果不符合上述条件,则找下一个可走的方块//来一个标志,标志是否找到下一个可走方块,find(0未找到,1找到)//进而进行下一步位移操作already_find = 0;//判断栈顶节点此时,是否还有方向可走while(find_direction < 4 && already_find == 0){find_direction++;switch(find_direction){//从左上角出发,向下是x(0~n),向右是y(0~n)case 0:find_X = depth_route.data[depth_route.top].x - 1;find_Y = depth_route.data[depth_route.top].y;break;case 1:find_X = depth_route.data[depth_route.top].x;find_Y = depth_route.data[depth_route.top].y + 1;break;case 2:find_X = depth_route.data[depth_route.top].x + 1;find_Y = depth_route.data[depth_route.top].y;break;case 3:find_X = depth_route.data[depth_route.top].x;find_Y = depth_route.data[depth_route.top].y - 1;break;}//判断探索的节点,是否可以前进if(mapper[find_X][find_Y] == 0){already_find = 1;}//在此while循环里,遍历此节点的所有方向,如果有通道,就可以走,跳出来开始去往下一个节点//如果已经遍历到最后一个方向 , 进来之后,也找不到下个可走方块,则赋值 already_find=0//此时是异常跳出}//判断是否找到下个可走方向if(already_find == 1){//找到,则把find_x,find_y坐标及其探索方向,入栈depth_route.data[depth_route.top].direction = find_direction;//栈顶指针加一depth_route.top++;depth_route.data[depth_route.top].x = find_X;depth_route.data[depth_route.top].y = find_Y;//路线栈顶节点,方向置空 为-1depth_route.data[depth_route.top].direction = -1;//如果通过上述验证,则此节点已经加入路线,占用地图,标记为 -1mapper[find_X][find_Y] = -1;}//如果没找到下一个可走节点,则把栈顶节点退栈,找回头路的节点的下一个方向继续探索else{mapper[depth_route.data[depth_route.top].x][depth_route.data[depth_route.top].y] = 0;depth_route.top--;//退栈则不保存出栈元素}}return 0;
}int main()
{int start_pointX;int start_pointY;int export_pointX;int export_pointY;bool result;for(int display_x = 1; display_x < X+1;display_x++){if(display_x == 1){printf(" →Y");printf("\t");for(int display_y = 1; display_y < Y+1;display_y++){printf("%d ",display_y);}printf("\n");printf("↓ X");printf("\n");}printf(" %d ",display_x);printf("\t");for(int display_y = 1; display_y < Y+1;display_y++){printf("%d ",mapper[display_x][display_y]);}printf("\n");}printf("\n请输入初始地址:\n(例如:1,1)");scanf("%d, %d", &start_pointX, &start_pointY);printf("\n请输入出口地址:\n(例如:8,8)");scanf("%d, %d", &export_pointX, &export_pointY);result = Find_path(start_pointX,start_pointY,export_pointX,export_pointY);if(result == 1){printf("此路有解!");}elseif(result == 0){printf("此路无解!");}return 0;
}
这篇关于深度优先遍历解决迷宫问题(顺序栈的应用)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
