栈与队列算法设计：(1)迷宫问题_迷宫问题的求解是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的

1.题目

  迷宫问题的求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔墙，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。设计算法实现迷宫求解。

2.题目分析

 算法分析

  1.这里我们使用的是栈来解决迷宫问题。
   对于迷宫问题，我们常规的思维是——试错，即先随便找一条路，一直走下去，直到走到尽头，如果无法抵达出口，我们便返回上一个分叉路口，继续试错，直到走到出口。这也是这道题的算法思想，不过今天我们来使用栈为我们保存我们试错的每一条路径。
   首先，我们需要定义三个结构：迷宫坐标、方向和保存路径坐标的栈。

#define StackSize 100

typedef struct POSITION
{
	int x;           //当前坐标的X值
	int y;           //当前坐标的Y值
	int Direction;   //当前坐标的指向下一坐标的方向
}Position,*PPosition;

typedef struct MOVEMENT
{
	int MoveX;       //移向下一坐标的X的变化值 
	int MoveY;       //移向下一坐标的Y的变化值
}MoveMent,*PMovement;

typedef struct POSITION_STACK
{
	Position PosStack[StackSize];  //栈，用来保存走过的坐标，每一个元素为一个Position结构体
	int Top;                       //栈顶指针
}PositionStack,*PPositionStack;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  2.第二步，我们初始化一个迷宫（自定义）。为了方便坐标的设定，这里我们使用二维数组来保存迷宫的每个坐标。同时，我们根据小老鼠每次行走的方向设置四个方向（上下左右），这里需要用到我们上面定义的结构体，并定义一个结构体数组，每个结构体表示一个方向（即X和Y变化的值）。

int Maze[MazeSize + 2][MazeSize + 2] =
	{

		{ 1,1,1,1,1,1,1,1,1,1 },
		{ 1,0,1,0,1,1,1,1,1,1 },
		{ 1,0,0,0,0,0,0,1,1,1 },
		{ 1,1,0,1,1,1,0,1,1,1 },
		{ 1,1,0,0,0,1,0,1,1,1 },
		{ 1,1,1,1,0,1,1,1,1,1 },
		{ 1,0,1,0,0,1,1,1,1,1 },
		{ 1,0,1,0,1,0,0,0,1,1 },
		{ 1,1,1,0,0,0,1,0,0,1 },
		{ 1,1,1,1,1,1,1,1,1,1 },
	};
	
//小老鼠每次移向下一坐标时，默认方向的选择顺序为上下左右
MoveMent MoveMent[4] = { {-1,0},{1,0},{0,-1},{0,1} };  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  3.第三步，我们从迷宫的（1，1）坐标处开始探寻路径。
   首先，由于当前处于（1，1）处，需定义一个结构体Position来保存当前的位置，并将其压入堆栈，同时我们需要定义临时变量来保存当前坐标和即将探寻的下一位坐标。
   接着，我们进入while循环，如果栈不为空，我们需要弹出栈顶坐标，来告诉我们需要出发的位置（后续试错时其主要作用）。同时临时变量获得栈弹出的当前坐标，同时方向初始为向上，这时，我们判断向上是否为通路，如果不通，则指向下一方向，直到找到通路。如图，我们当前位于（1，1），判断方向后，下方坐标（2，1）为通路。这时，我们将临时变量赋值给结构体并压入栈中，同时判断这个坐标是否为终点，如果不是，则当前位置移动到（2，1），重新再从上下左右四个方向判断通路。
   这里可能会有人发现问题了，我们的（1，1）也是通路，如果当前坐标（2，1）向上方判断时，不就出现回头的尴尬情况了吗？所以，这里也是迷宫问题的一个关键点，即不“走回头路”。所以，我们这里采取的办法为：将走过的坐标在二维数组中的值设置为-1，这样也就解决了我们担心的问题。

  4.经过一系列的循环，我们走出了这样一条路径。
   如图，我们走进了一条死胡同，即当前坐标（7，1）的四个方向都无法继续移动。这时，我们需要进行的操作是，弹出栈顶坐标（7，1），同时当前位置指向这一坐标，即我们所称的“退位”。然后再判断当前位置的四个方向有无通路，如果有，则继续压入栈中，继续移动；否则，继续弹出栈顶坐标，直到返回到上一个分岔路口。
   返回到分岔路口后，我们找到了另一个可行的通道，接着我们继续重复上面的循环，压栈…出栈…直到找到最后的出口。

 算法实现

BOOL FindMazePath(int (&Maze)[MazeSize + 2][MazeSize + 2], PositionStack &PositionStack)
{
	MoveMent MoveMent[4] = { {-1,0},{1,0},{0,-1},{0,1} };   //四个方向 上下左右
	Position CurrentPos = { 1,1,-1 };                       //初始坐标
	Maze[1][1] = -1;                                        //设置为-1，表示已到过该坐标
	int NextX, NextY;
	int CurrentX, CurrentY, Direction;                      //临时变量，用于保存当前坐标和下一坐标
	PushData(PositionStack, CurrentPos);

	while (PositionStack.Top != -1)
	{
	    //获取当前栈顶的坐标
		CurrentPos = PopData(PositionStack);
		CurrentX = CurrentPos.x;
		CurrentY = CurrentPos.y;
		Direction = CurrentPos.Direction + 1;
		//按上下左右的顺序查看四个方向是否有通路
		while (Direction < 4)
		{
		    //保存下一坐标
			NextX = CurrentX + MoveMent[Direction].MoveX;
			NextY = CurrentY + MoveMent[Direction].MoveY;
			//如果有通路
			if (Maze[NextX][NextY] == 0)
			{
			    //压栈，同时当前坐标指向该坐标
				PushData(PositionStack, CurrentPos);
				CurrentPos.x = NextX;
				CurrentPos.y = NextY;
				CurrentX = NextX;
				CurrentY = NextY;
				//该坐标已到达
				Maze[CurrentX][CurrentY] = -1;
				//如果到达终点
				if (CurrentX == MazeSize && CurrentY == MazeSize)
				{
				    //输出路径
					PushData(PositionStack, CurrentPos);
					for (int i = 0; i < PositionStack.Top; i++)
					{
						printf("(%d,%d)->", PositionStack.PosStack[i].x, PositionStack.PosStack[i].y);
					}
					printf("(%d,%d)", PositionStack.PosStack[PositionStack.Top].x, PositionStack.PosStack[PositionStack.Top].y);
					return TRUE;
				}
				else
				{
				    //如果没有到达终点，则继续重新从四个方向查找通路
					Direction = 0;
				}

			}
			else
			{
			    //如果当前方向不同，转向下一方向
				Direction++;
			}

		}
	}
	
}
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

3.参考代码

#include<Windows.h>
#include<tchar.h>
#include <iostream>
using namespace std;

#define MazeSize  8
#define StackSize 100

typedef struct POSITION
{
	int x;
	int y;
	int Direction;
}Position,*PPosition;

typedef struct MOVEMENT
{
	int MoveX;
	int MoveY;
}MoveMent,*PMovement;

typedef struct POSITION_STACK
{
	Position PosStack[StackSize];
	int Top;
}PositionStack,*PPositionStack;

BOOL PushData(PositionStack &PositionStack, Position Position)
{
	if (PositionStack.Top == StackSize - 1)
	{
		return FALSE;
	}
	else
	{
		PositionStack.Top++;
		PositionStack.PosStack[PositionStack.Top].x = Position.x;
		PositionStack.PosStack[PositionStack.Top].y = Position.y;
		PositionStack.PosStack[PositionStack.Top].Direction = Position.Direction;
		return TRUE;
	}
}

Position PopData(PositionStack &PositionStack)
{
	if (PositionStack.Top == -1)
	{
	}
	else
	{
		Position v1 = PositionStack.PosStack[PositionStack.Top];
		PositionStack.Top--;
		return v1;
	}
}

BOOL FindMazePath(int (&Maze)[MazeSize + 2][MazeSize + 2], PositionStack &PositionStack)
{
	MoveMent MoveMent[4] = { {-1,0},{1,0},{0,-1},{0,1} };   //四个方向 上下左右
	Position CurrentPos = { 1,1,-1 };                       //初始坐标
	Maze[1][1] = -1;                                        //设置为-1，表示已到过该坐标
	int NextX, NextY;
	int CurrentX, CurrentY, Direction;                      //临时变量，用于保存当前坐标和下一坐标
	PushData(PositionStack, CurrentPos);
	while (PositionStack.Top != -1)
	{
	    //获取当前栈顶的坐标
		CurrentPos = PopData(PositionStack);
		CurrentX = CurrentPos.x;
		CurrentY = CurrentPos.y;
		Direction = CurrentPos.Direction + 1;
		//按上下左右的顺序查看四个方向是否有通路
		while (Direction < 4)
		{
		    //保存下一坐标
			NextX = CurrentX + MoveMent[Direction].MoveX;
			NextY = CurrentY + MoveMent[Direction].MoveY;
			//如果有通路
			if (Maze[NextX][NextY] == 0)
			{
			    //压栈，同时当前坐标指向该坐标
				PushData(PositionStack, CurrentPos);
				CurrentPos.x = NextX;
				CurrentPos.y = NextY;
				CurrentX = NextX;
				CurrentY = NextY;
				//该坐标已到达
				Maze[CurrentX][CurrentY] = -1;
				//如果到达终点
				if (CurrentX == MazeSize && CurrentY == MazeSize)
				{
				    //输出路径
					PushData(PositionStack, CurrentPos);
					for (int i = 0; i < PositionStack.Top; i++)
					{
						printf("(%d,%d)->", PositionStack.PosStack[i].x, PositionStack.PosStack[i].y);
					}
					printf("(%d,%d)", PositionStack.PosStack[PositionStack.Top].x, PositionStack.PosStack[PositionStack.Top].y);
					return TRUE;
				}
				else
				{
				    //如果没有到达终点，则继续重新从四个方向查找通路
					Direction = 0;
				}
			}
			else
			{
			    //如果当前方向不同，转向下一方向
				Direction++;
			}
		}
	}
}
int main()
{
	int Maze[MazeSize + 2][MazeSize + 2] =
	{

		{ 1,1,1,1,1,1,1,1,1,1 },
		{ 1,0,1,0,1,1,1,1,1,1 },
		{ 1,0,0,0,0,0,0,1,1,1 },
		{ 1,1,0,1,1,1,0,1,1,1 },
		{ 1,1,0,0,0,1,0,1,1,1 },
		{ 1,1,1,1,0,1,1,1,1,1 },
		{ 1,0,0,0,0,1,1,1,1,1 },
		{ 1,0,1,0,1,0,0,0,1,1 },
		{ 1,1,1,0,0,0,1,0,0,1 },
		{ 1,1,1,1,1,1,1,1,1,1 },
	};
	PositionStack PositionStack;
	PositionStack.Top = -1;
	
	FindMazePath(Maze, PositionStack);

}
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

4.测试结果