学习贺利坚老师课程
数据结构例程——迷宫问题(用栈结构)_数据结构迷宫问题-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("此路有解!");
}
else
if(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;
//路线栈顶节点,方向置空 为-1
depth_route.data[depth_route.top].direction = -1;
//如果通过上述验证,则此节点已经加入路线,占用地图,标记为 -1
mapper[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("此路有解!");
}
else
if(result == 0)
{
printf("此路无解!");
}
return 0;
}