c语言数据结构之迷宫求解

2024-01-07 08:12| 来源: 网络整理| 查看: 265

现在网上各种对于迷宫的求解，版本多的数不胜数。本人小白一枚，贴上自己对迷宫的求解这个小项目，自己写的。望能帮助一些同样有困难的人，毕竟我当时费解了好一会儿时间呢。。。

首先，先标明对于迷宫求解这个项目，首先我提出自己的思路，利用“穷举求解”的方法（严蔚敏老师数据结构一书中提到，一开始不知方法其名。）其实简单来说就是一条路一条路去试，当然不能随便试，我的方法是按照从入口出发，顺一个方向向前探索，走得通就继续向前走；否则留下标记沿原路退回并换一个方向继续探索，直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构（对于栈并没有详细阐述）。

//调用头文件 #ifndef AFXSTD_H #define AFXSTD_H #include #include #include #include using namespace std; // cout; cin;C++的输入输出 #endif //迷宫的结构体的创建 #ifndef MAZE_H #define MAZE_H #define ROWSIZE 10 //迷宫大小 #define COLSIZE 10 #define Reachable 0 //可以到达的结点 #define Bar 1 //障碍物 #define Foot 2 //足迹 #define Mark 3 //不可通路标记 typedef int MapType[ROWSIZE][COLSIZE]; // 地图类型 typedef struct { int row;// x int col;// y; }PosType; //坐标结构体 typedef struct { int ord; //通道块在道路上的序号 PosType seat; //小人坐标 int di; // 方向 // 1 2 3 4 }MElemType; //试迷宫小人的结构 typedef MElemType SElemType; // 和stack 关联 bool MazePass(MapType maze,PosType curpos); void FootPrint(MapType maze,PosType curpos); //足迹打印 PosType NextPos(PosType curpos,int di); //下一个位置 void MarkPrint(MapType maze,PosType curpos); //打印不可通标记 bool MazePath(MapType maze,PosType start,PosType end); //迷宫解谜核心 void PrintMap(MapType maze); //打印地图 #endif //栈的结构体 #include"Maze.h" #ifndef SEQSTACK_H #define SEQSTACK_H #define STACKSIZE 100 //typedef int SElemType; struct SeqStack { SElemType *data; int maxsize; int top; }; void Init_Stack(SeqStack &st); void Destroy_Stack(SeqStack &st); void Stack_Clear(SeqStack &st); bool Stack_Empty(SeqStack &st); bool Stack_Full(SeqStack &st); int Stack_Size(SeqStack &st); bool Stack_Push(SeqStack &st,const SElemType &x); bool Stack_Pop(SeqStack &st, SElemType &x); SElemType GetTop(SeqStack &st); void Pop(SeqStack &st); #endif

以上是头文件的创建，和结构体的创建，现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑，切记切记！！

现在贴出函数的代码，解释我会尽力都写清楚。（栈的问题我后续会重新再仔细阐述的，这次的重点在于迷宫的求解，所以直接贴出栈的详细代码，望谅解。。）

//这里是栈的实现代码 #include"AfxStd.h" #include"Stack.h" bool Stack_Resize(SeqStack &st) { SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2); if(NULL == s) return false; for(int i = 0;i

【本文地址】

公司简介

联系我们

c语言 数据结构之迷宫求解

c语言数据结构之迷宫求解