DiDong's Blog

0%

迷宫求解 (所有路径)

Posted on Edited on In
Symbols count in article: 5.4k Reading time ≈ 5 mins.

迷宫问题

对于如下所示的迷宫，如何找到所有路径？（ # 为墙，* 为出口，0 为入口）（注意：要找到所有的路径必须保证一条路径不能在同一个位置走两次及两次以上，反之，一方面，这样没有意义；另一方面，这样可能会造成在一个地方一直转圈）

迷宫示例

大致思路（试错法）

  1. 先将迷宫用二维数组表示，0代表围墙，1代表通路，2代表出口，而入口通过坐标指定

  2. 定义位置类LocDir，成员X（列坐标）和Y（行坐标）代表在迷宫某个位置的坐标,成员dir代表在这个位置后下一步要走的方向（1代表向上，2代表向右，3代表向下，4代表向左）

  3. 先定义一个入口的位置对象；而后创建一个栈（存放位置对象），用于记录走过的路径，并将入口进栈。

  4. 从入口开始，根据位置对象中的方向，在向该方向移动前先判断：若为0，说明前方是墙，此时将方向+1，即调整方向；若为1，说明前方是通路，则将现在位置在二维数组中的值置0，表示走过的路已经变成了墙，不能走回头路（避免出现文章开头提出的现象），向前方移动，并将到达的位置X和Y记录下来，dir置1，表示先试着向上走，将该位置对象入栈；若为2，说明找到了出口，这个时候将路径以坐标的形式输出即可。

  5. 若4中调整方向后，直到方向变成4，即向左走也不行，则此时应该将方向+1，变为5，但这样就找不到方向了，说明在该位置四周都是墙，此时将栈顶元素退栈，同时将其变为现在的位置，即沿原路径返回了一步；再将现在位置在二维数组中的值置1，即将这个位置变为通路；最后将方向+1。

  6. 还可以将每次找到的正确路径的长度记录下来，通过比较，输出最长路径（之一）和最短路径（之一）

总结

总的来说，迷宫求解试错法的关键在于，在迷宫的每个位置，我们都有四个方向可以选择，那么，只需要在每个位置将这四个方向依次试过，就可以确保走过迷宫的每一个位置，且单条路径不会重复走过同一个位置。

实现代码

注：由于代码中使用的栈是我自定义的，故栈中的一个函数Exchangge(top)（用来替换栈顶元素），在标准栈中可能并没有，但其本质是将原栈顶元素出栈后再将新的元素进栈，即可分成两步写。

main.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
#include<Windows.h>
#include"MazeSolve.h"
#include"LocDir.h"

int main() {
	//0代表围墙，1代表通路，2代表出口
	int map[10][10] = {
		{0,0,0,0,0,0,0,0,0,0},
		{0,1,1,0,1,1,1,0,1,0},
		{0,1,1,0,1,1,1,0,1,0},
		{0,1,1,1,1,0,0,1,1,0},
		{0,1,0,0,0,1,1,1,1,0},
		{0,1,1,1,0,1,1,1,1,0},
		{0,1,0,1,1,1,0,1,1,0},
		{0,1,0,0,0,1,0,0,1,0},
		{0,0,1,1,1,1,1,1,2,0},
		{0,0,0,0,0,0,0,0,0,0} 
	};
	//入口初始化
	LocDir in;
	in.X = 1;
	in.Y = 1;
	in.dir = 1;

	MazeSolve(map, in);

	system("pause");
	return 0;
}

MazeSolve.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
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
#ifndef _MAZESOLVE_H
#define _MAZESOLVE_H

#include"LinkStack.h"
#include"LocDir.h"
#include<iostream>

using namespace std;

void MazeSolve(int map[][10], const LocDir & in) {
	int roadNum = 0;
	int roadLen[200] = { 0 };

	LinkStack<LocDir> LocDirStack;
	
	LocDirStack.Push(in);

	LocDir top, temp;
	LocDirStack.Top(top);

	while (!(top.X==1&&top.Y==1&&top.dir==5)) {
		//Move
		switch (top.dir)
		{
		case 1://turn up
			if (map[top.Y-1][top.X]) {
				if (map[top.Y - 1][top.X] == 2) {
					cout << "Road" << roadNum << ':';
					cout << '(' << top.X << ',' << top.Y-1 << ')' << '\t';
					roadLen[roadNum] = 1 + LocDirStack.GetSize();
					roadNum++;
					LocDirStack.Show();
					cout << endl;
					top.dir++;
					LocDirStack.Exchange(top);
					break;
				}
				map[top.Y][top.X] = 0;
				temp = { top.X,top.Y - 1,1 };
				LocDirStack.Push(temp);
			}
			else {
				top.dir++;
				LocDirStack.Exchange(top);
			}
			break;
		case 2://turn right
			if (map[top.Y][top.X + 1]) {
				if (map[top.Y][top.X + 1] == 2) {
					cout << "Road" << roadNum << ':';
					cout << '(' << top.X+1 << ',' << top.Y << ')' << '\t';
					roadLen[roadNum] = 1 + LocDirStack.GetSize();
					roadNum++;
					LocDirStack.Show();
					cout << endl;
					top.dir++;
					LocDirStack.Exchange(top);
					break;
				}
				map[top.Y][top.X] = 0;
				temp = { top.X+1,top.Y,1 };
				LocDirStack.Push(temp);
			}
			else {
				top.dir++;
				LocDirStack.Exchange(top);
			}
			break;
		case 3://turn down
			if (map[top.Y+1][top.X]) {
				if (map[top.Y + 1][top.X] == 2) {
					cout << "Road" << roadNum << ':';
					cout << '(' << top.X << ',' << top.Y + 1 << ')' << '\t';
					roadLen[roadNum] = 1 + LocDirStack.GetSize();
					roadNum++;
					LocDirStack.Show();
					cout << endl;
					top.dir++;
					LocDirStack.Exchange(top);
					break;
				}
				map[top.Y][top.X] = 0;
				temp = { top.X,top.Y + 1,1 };
				LocDirStack.Push(temp);
			}
			else {
				top.dir++;
				LocDirStack.Exchange(top);
			}
			break;
		case 4://turn left
			if (map[top.Y][top.X - 1]) {
				if (map[top.Y][top.X - 1] == 2) {
					cout << "Road" << roadNum << ':';
					cout << '(' << top.X -1<< ',' << top.Y<< ')' << '\t';
					roadLen[roadNum] = 1 + LocDirStack.GetSize();
					roadNum++;
					LocDirStack.Show();
					cout << endl;
					top.dir++;
					LocDirStack.Exchange(top);
					break;
				}
				map[top.Y][top.X] = 0;
				temp = { top.X - 1,top.Y,1 };
				LocDirStack.Push(temp);
			}
			else {
				top.dir++;
				LocDirStack.Exchange(top);
			}
			break;
		default://no choice
			LocDirStack.Pop(temp);

			LocDirStack.Top(top);
			top.dir++;
			LocDirStack.Exchange(top);

			map[top.Y][top.X] = 1;

			break;
		}

		LocDirStack.Top(top);
	}

	roadNum = 0;
	int minRoad = roadLen[roadNum],maxRoad = roadLen[roadNum];
	int minRoadPos =0, maxRoadPos = 0;
	while (roadLen[roadNum]) {
		if (minRoad > roadLen[roadNum]) {
			minRoad = roadLen[roadNum];
			minRoadPos = roadNum;
		}
		if (maxRoad < roadLen[roadNum]) {
			maxRoad = roadLen[roadNum];
			maxRoadPos = roadNum;
		}
		++roadNum;
	}
	cout << "Min RoadNum:" << minRoadPos << '\t' << "Min RoadLength:" << minRoad << endl;
	cout << "Max RoadNum:" << maxRoadPos << '\t' << "Max RoadLength:" << maxRoad << endl;
}

#endif // !_MAZESOLVE_H

LocDir.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
#ifndef _LOCDIR_H
#define _LOCDIR_H

#include<iostream>

using namespace std;

class LocDir
{
public:
	LocDir(int X=0, int Y=0, int dir=0);
	friend ostream& operator<<(ostream& out,const LocDir& loc_dir);
	~LocDir();
	int X;
	int Y;
	int dir;
private:

};

LocDir::LocDir(int X,int Y,int dir):X(X),Y(Y),dir(dir)
{
}

LocDir::~LocDir()
{
}


ostream& operator<<(ostream& out, const LocDir& loc_dir)
{
	out << '(' << loc_dir.X << ',' << loc_dir.Y << ')' << '\t';
	return out;
}

#endif // !_LOCDIR_H
Thank you for your reward !