现在网上各种对于迷宫的求解，版本多的数不胜数。本人小白一枚，贴上自己对迷宫的求解这个小项目，自己写的。望能帮助一些同样有困难的人，毕竟我当时费解了好一会儿时间呢。
首先，先标明对于迷宫求解这个项目，首先我提出自己的思路，利用“穷举求解”的方法（严蔚敏老师数据结构一书中提到，一开始不知方法其名。）其实简单来说就是一条路一条路去试，当然不能随便试，我的方法是按照从入口出发，顺一个方向向前探索，走得通就继续向前走；否则留下标记沿原路退回并换一个方向继续探索，直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构（对于栈并没有详细阐述）。
|
1
2
3
4
5
6
7
8
9
10
11
|
//调用头文件
#ifndef AFXSTD_H
#define AFXSTD_H
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
using namespace std;
// cout; cin;C++的输入输出
#endif
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
//迷宫的结构体的创建
#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
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//栈的结构体
#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
|
以上是头文件的创建，和结构体的创建，现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑，切记切记！！
现在贴出函数的代码，解释我会尽力都写清楚。（栈的问题我后续会重新再仔细阐述的，这次的重点在于迷宫的求解，所以直接贴出栈的详细代码，望谅解。）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
//这里是栈的实现代码
#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<= st.top;++i)
{
s[i] = st.data[i];
}
free(st.data);
st.data = s;
st.maxsize = st.maxsize * 2;
return true;
}
void Init_Stack(SeqStack &st)
{
st.maxsize = STACKSIZE;
st.top = -1;
st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize);
if(NULL == st.data)
{
exit(0);
}
}
void Destroy_Stack(SeqStack &st)
{
free(st.data);
st.data = NULL;
st.maxsize = 0;
st.top = -1;
}
void Stack_Clear(SeqStack &st)
{
st.top = -1;
}
bool Stack_Empty(SeqStack &st)
{
return Stack_Size(st) == 0;
}
bool Stack_Full(SeqStack &st)
{
return Stack_Size(st) == st.maxsize;
}
int Stack_Size(SeqStack &st)
{
return st.top + 1;
}
bool Stack_Push(SeqStack &st,const SElemType &x)
{
if(Stack_Full(st) && ! Stack_Resize(st))
{
return false;
}
st.data[++st.top] = x;
return true;
}
bool Stack_Pop(SeqStack &st, SElemType &x)
{
if(Stack_Empty(st))
{
return false;
}
x = st.data[st.top--];
return true;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
//调用前面创建的头文件
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"
/////////////////////////////////////////////////
bool MazePass(MapType maze,PosType curpos) //判断是否可以通过
{
return maze[curpos.row][curpos.col] == Reachable; //判断当前结点是否能通过
}
void FootPrint(MapType maze,PosType curpos) //打印足迹
{
maze[curpos.row][curpos.col] = Foot;
}
PosType NextPos(PosType curpos,int di) //对下一个结点方向的判断
{
switch(di)
{
case 1: curpos.row+=1; break;// 1
case 2: curpos.col-=1; break;// 2
case 3: curpos.row-=1; break;// 3
case 4: curpos.col+=1; break;// 4
}
return curpos;
}
void MarkPrint(MapType maze,PosType curpos) //不能通过的结点留下不能通过的标记
{
maze[curpos.row][curpos.col] = Mark;
}
bool MazePath(MapType maze,PosType start,PosType end)//（核心）迷宫解谜
{
bool res = false; //定义一个res参数为布尔型
PosType curpos = start; //初始当前位置为入口
int curstep = 1; // 初始探索方向为1
SeqStack st; //路径存储栈
MElemType e; //初始探索小人
Init_Stack(st); //初始化栈
do{
if(MazePass(maze,curpos)) //当前位置可通过，即是未曾走到过的坐标
{
FootPrint(maze,curpos); //留下足迹
e.di = 1, e.seat = curpos,e.ord = curstep++;
Stack_Push(st,e); //加入路径中
if(curpos.row == end.row && curpos.col == end.col)
{
res = true;
break;
} //到达终点
curpos = NextPos(curpos,1); //探索下一位置
}
else
{
if(!Stack_Empty(st)) //当前位置不能通过
{
Stack_Pop(st,e);
while(e.di == 4 && !Stack_Empty(st))
{
MarkPrint(maze,e.seat);
Stack_Pop(st,e); // 留下不能通过的标记，并退回一步
}
if(e.di < 4)
{
e.di+=1; // 换下一个方向探索
Stack_Push(st,e); //再次记录路径
curpos = NextPos(e.seat,e.di); // 当前位置设为新方向的相邻块
}
}
}
}while(!Stack_Empty(st)); //当栈空摧毁栈，返回失败参数
Destroy_Stack(st);
return res;
}
void PrintMap(MapType maze) //打印地图
{
for(int i = 0;i<ROWSIZE;++i)
{
for(int j = 0;j<COLSIZE;++j)
{
printf("%2d",maze[i][j]);
}
printf("\n");
}
printf("\n");
}
|
以上就是迷宫的详细解释，希望能帮助到大家。后面再添加我的测试文件。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include"AfxStd.h"
#include"Maze.h"
int main()
{
MapType maze ={ //一开始地图的创建
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,1,1,1,1,0,1},
{1,0,1,1,1,1,0,0,0,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
PosType start={1,1},end={8,8};
PrintMap(maze); //打印初始地图
MazePath(maze,start,end);
PrintMap(maze); //打印迷宫解法
return 0;
}
|
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_38361756/article/details/81136701