迷宫求解

从入口进入开始， 向不同方向试探，走到死胡同就退回。

找迷宫通路需要使用回溯法，找迷宫通路是对回溯法的一个很好的应用，实现回溯的过程用到数据结构—栈！

回溯法：

​ 对一个包括有很多个结点，每个结点有若干个搜索分支的问题，把原问题分解为若干个子问题求解的 算法；当搜索到某个结点发现无法再继续搜索下去时，就让搜索过程回溯(回退)到该节点的前一个结点，继续 搜索该节点外的其他尚未搜索的分支；如果发现该结点无法再搜索下去，就让搜索过程回溯到这个结点的前一 结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或者搜索完了全部可搜索分支没有解存 在为止

思路&解释

二维数组作为地图。

一开始确定一个入口——需要判定入口是否合法。

先将入口位置坐标压入栈，只要栈中不为空，那么每次判断移动方向前都要判断当前位置是不是出口。然后由此坐标开始向四周判断，判断哪有路可以走，是路就开始移动(cur-当前位置),压进栈……,走到死胡同，说明四周都不能走了，开始边popStack边向四周判断，不放过来时路上的任何一个遗漏的可能出口路径，反之，找到出口直接return true。如果该迷宫没有出口，结果栈中的元素将被全部pop出来，栈空，return false;

相关细节如下代码所示

图示

迷宫求解

实际探索路径中，有的”胡同没去探索”。

maze.h

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#pragma once
#include<iostream>
using namespace std;


#define MAX_SIZE 128

typedef struct _Postion//地图中点的坐标,这个栈中存的元素就是点的坐标
{
	int _x;
	int _y;
}Postion;

typedef Postion DataType;


//栈的结构体
typedef struct _Stack
{
	DataType* top;	
	DataType* base;
}Stack;

//栈的初始化
bool initStack(Stack& S)
{
	S.base = new DataType[MAX_SIZE];
	if (!S.base)
	{
		return false;
	}
	S.top = S.base;
	return true;
}

//入栈
bool pushStack(Stack& S, DataType data)
{
	if (!S.base)
	{
		return false;
	}
	if (S.top - S.base == MAX_SIZE)
	{
		return false;
	}

	*(S.top) = data;
	S.top++;
	return true;
}

//出栈
bool popStack(Stack& S,DataType& e)
{
	if (S.top == S.base)
	{
		return false;
	}
	e = *(--S.top);
	return true;
}

//返回栈顶元素         
DataType* getTop(Stack& S)
{
	if (S.top - S.base == 0)
	{
		return NULL;
	}
	//注意何时自增何时不自增
	return S.top-1;//返回栈顶元素的指针
}

//返回栈中元素个数
int getSize(Stack& S)
{
	return S.top - S.base;
}

//判断栈是否为空
bool isEmpty(Stack& S)
{
	if (S.top == S.base)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//销毁栈
void destoryStack(Stack& S)
{
	if (S.base)
	{
		delete[] S.base;
		S.top = S.base = NULL;
	}
}

maze.cpp

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include<iostream>
#include<assert.h>
#include"maze.h"
using namespace std;

#define ROW  6//行
#define COL  6//列

//地图
typedef struct _Maze
{
	int map[ROW][COL];
}Maze;

//根据给出给出的地图数据初始化结构体地图
void initMaze(Maze& m, int map[ROW][COL])
{
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			m.map[i][j] = map[i][j];
		}
	}
}

//打印迷宫(地图)
void printMaze(Maze& m)
{
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			cout << m.map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

//判断是否是有效的入口
bool isValidEnter(Maze* m,Postion enter)
{
	assert(m);//断言-里面的表达式为0直接终止程序,注意里面的内容是什么
	//只要入口在四个边界上就是合法的,并且是1(道路)
	if (((enter._x == 0 || enter._x == ROW - 1) || (enter._y == 0 || enter._y == COL - 1)))
	{
		return true;
	}
	return false;
}

//判断当前位置是否是出口
bool isVaildExit(Maze* m, Postion cur, Postion enter)
{
	assert(m);
	//该结点不能是入口点，除了入口点，在边界上就是合法出口

	if ((cur._x != enter._x || cur._y != enter._y) && ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1)))
	{
		return true;
	}
	else
	{
		return false;
	}
}

//判断当前结点的下一个结点是否能走通-是不是可以走的点
bool isNextPass(Maze* m, Postion cur, Postion next)
{
	assert(m);
	//判断next是不是cur的下一个结点
	//同一行相邻或者同一列相邻
	if (((next._x == cur._x) && ((next._y == cur._y + 1) || (next._y == cur._y - 1)))
		|| ((next._y == cur._y) && ((next._x = cur._x + 1) || (next._x = cur._x - 1))))
	{
		//确实是cur的下一个结点(相邻的 )
		//判断这个点是不是在迷宫里
		//合法坐标并且那个位置的值是1
		if (((next._x >= 0 && next._x < ROW) && (next._y >= 0 && next._y < COL)) 
			&& (m->map[next._x][next._y] == 1))
			//最后的参数==1，不仅仅是看是否是可以走的位置(道路是1)，
			//同时有了这个我们就不用倒着往往前走了(不走重复的路)，不是有效的结点不只是墙(0)
			//走过的也不是有效结点，直接pop出栈，通过出栈来往前回退
		{
			return true;
		}
	}
	return false;
}

//寻找迷宫通路
bool PassMaze(Maze* m, Postion enter, Stack& s)
{
	assert(m && isValidEnter(m, enter));

	Postion cur = enter;//cur存储当前结点
	Postion next;//下一个结点，从入口开始出发向四周移动

	//先将入口压入栈中
	pushStack(s, cur);
	m->map[cur._x][cur._y] = 2;//将入口值改为2

	//循环求解-当栈中还有路径时
	while (!isEmpty(s))
	{
		cur = *getTop(s);//取到栈顶元素
		//判断当前位置是否是出口
		if (isVaildExit(m, cur, enter))//注意参数传递顺序
		{
			return true;//是出口直接返回
		}
		
		//不是出口继续在周围判断
		//把cur当前刚才那个位置拿过来向四周判断
		
		//先向左判断
		next = cur;
		next._y = cur._y - 1;
		if (isNextPass(m,cur,next))//如果下一个结点走得通
		{
			//走得通就走到那个位置-压进栈
			pushStack(s, next);
			//走过的位置-标记
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;

			//之后
			continue;
		}
		//走不通向另一个方向判断
		//向右走一步
		next = cur;
		next._y = cur._y + 1;
		if (isNextPass(m, cur, next))
		{
			pushStack(s, next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
			continue;
		}

		//向下走一步
		next = cur;
		next._x = cur._x + 1;
		if (isNextPass(m, cur, next))
		{
			pushStack(s, next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
			continue;
		}

		//向上走一步
		next = cur;
		next._x = cur._x - 1;
		if (isNextPass(m, cur, next))
		{
			pushStack(s, next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
			continue;
		}

		//走到这里说明此结点的四个方向都走不通
		//进行回溯
		Postion tmp;//没用 临时接收
		popStack(s, tmp);//出栈

	}
	return false;
}

int main(void)
{
	//0-墙 1-路
	int map[ROW][COL] = {
		0,0,1,0,0,0,
		0,0,1,1,1,0,
		0,0,1,0,0,0, 
		0,1,1,1,1,0,
		0,0,1,0,1,0,
		0,0,0,0,1,0 
	};


	Maze m;//创建一个迷宫(地图)
	initMaze(m, map);//初始化迷宫
	printMaze(m);//打印迷宫

	cout << "_______" << endl;

	//迷宫入口
	Postion enter;
	enter._x = 0;
	enter._y = 2;

	//定义栈
	Stack s;//用于保存走过的轨迹，便于回溯
	initStack(s);//初始化栈

	int ret = PassMaze(&m, enter, s);
	if (ret)
	{
		cout << "有解" << endl;
	}
	else
	{
		cout << "无解" << endl;
	}
	printMaze(m);


	return 0;
}

结果

image-20211015144121027

注意

1.指针自增情况

2.参数传递顺序

3.F5是个好东西