关于用栈和队列分别解决走迷宫问题

对于生活中最常见的小游戏——走迷宫，相信大家都不陌生，人为走相信大家都会走，但能不能用代码实现，我们认为是可以的，以下是我们对如何走迷宫的一些看法和代码实现（cz负责队列解决，mml负责用栈解决）

1.关于用队列解决：

先简单介绍一下队列：队列是一种操作受限的线性表，只允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一段称为队尾，可进行删除的一端称为队头。队列的主要特点就是先进先出。依照存储结构可
分为顺序队和链式队。
解决思路：对于一个迷宫，我们将起点设置为（1，1），终点设置为（M，N），通路为0，不通路为1。对于当前位置我们知道可以往上，下，左，右四个方向行走，我们默认按照上，右，下，左的顺序依次查找可走的方向，将可以走的方格存入队列中，当四个方向查找完毕后，弹出队首元素从而开始对存入队列中的下一个元素进行可通路查找，当目前的队首元素恰好等于终点坐标时，即为找到终点（M，N）。如果队列已空且还没有找到终点，则该迷宫没有终点。那么到此已经解决了如何找到迷宫出路的大体方法，既然找到，又该如何输出呢？对此，我们认为可以在存储方格坐标的数据类型中加一个用来存储上一方格在队列中的位置下标pre（默认起点下标为-1），那么输出路径时就可以通过寻找上一方格的位置下标输出相应队列元素。例如：起点（1，1）的右方向假如是通路，那么存入队列中的元素为（1，2）且该元素pre=0.为什么可以采用这种方法？相信会有人问队列元素不是被弹出了吗？怎么输出队列中元素？其实对于这种问题队列中的顺序队存储方式就能很好解决：在对顺序队进行操作时弹出元素只是将头位置加1，而并非真正意义上的弹出，在这种情况下就能很好的保留之前所存入通路坐标，进而解决迷宫问题，如下图（图片引用自PPT——栈与队列）：

以下是代码的具体实现：

#include<iostream>
#define Maxsize 10000 //定义一个存储数据最大区间
using namespace std;
typedef struct
{
	int x;	//横坐标
	int y;	//纵坐标
	int pre;
}Box2;`	//定义一个数据类型存储位置信息
typedef struct
{
	Box2 data[Maxsize];	//队列存储的数据类型
	int front;	//队列头
	int rear;	//队列尾
}Queue;	//定义一个队列，该队列为顺序队列
int mg[1002][1002];	//定义一个存放迷宫的二维数组
void CreateQueue(Queue*& q)
{
	q = new Queue;
	q->front = q->rear = -1;
}	//为新队列申请存储空间
void EnQueue(Queue*& q, Box2 x)
{
	if (q->rear == Maxsize - 1)
	{
	cout << "存储失败！" << endl;
	return;
	}	//判断队列是否已满
	q->rear++;
	q->data[q->rear] = x;
	return;
}	//将新的可通方格存入队列中
void OutQueue(Queue*& q, Box2& x)
{
	if (q->front == q->rear)
	{
	cout << "读取失败！" << endl;
	return;
	}	//判断队列是否为空
	q->front++;
	x = q->data[q->front];
	return;
}
int QueueEmpty(Queue* q)
{
	return (q->front == q->rear);
}	//判断队列是否为空，若为空则返回1，否则返回0
void Cout(Queue* q, int front)
{
	int x = front;
	int i;
	do {
	i = x;
	x = q->data[x].pre;
	q->data[i].pre = -1;
	} while (x != 0);	//通过循环分别将从终点开始的前一位置记为-1
	x = 0;
	while (x < Maxsize)
	{
	if (q->data[x].pre == -1)
	{
	cout << "( " << q->data[x].x << " , " << q->data[x].y << " )" << endl;
	}
	x++;
	}	//遍历队列，将队列中数据为-1的坐标输出
}
void SearchPath(int x1, int y1, int x2, int y2)
{
	Box2 e;
	Queue *q;
	int i, j;
	CreateQueue(q);
	e.x = x1;
	e.y = y1;
	e.pre = -1;	//由于起点无前一位置，因此将起点前一位置定为-1
	EnQueue(q, e);	//将迷宫起点存入队列中
	mg[x1][y1] = 1; //将起点值改为1，避免重复进入
	while (!QueueEmpty(q))
	{
	OutQueue(q, e);	//判断队列中下一方格的通路情况
	i = e.x;
	j = e.y;
	if (i == x2 && j == y2)
	{
	Cout(q, q->front);
	delete q;
	return;
	}	//判断该方格是否为终点
	for (int m = 0; m < 4; m++)
	{
	int x, y;
	switch (m)
	{
	case 0:
	x = i - 1;
	y = j;
	break;
	case 1:
	x = i;
	y = j + 1;
	break;
	case 2:
	x = i + 1;
	y = j;
	break;
	case 3:
	x = i;
	y = j - 1;
	break;
	}
	if (mg[x][y] == 0)
	{
	e.x = x;
	e.y = y;
	e.pre = q->front;	//将可通方格的前一位置记为当前方格的存入队列中顺序
	EnQueue(q, e);
	mg[x][y] = 1;
	}	//将当前方格四个方向所有可通路存入队列中
	}
	}
	putchar('\n');
	cout << "Not Found";	//迷宫查找结束，未能找到终点
	delete q;
}
int main()
{
	int M, N, i, j;
	cin >> M >> N;	//输入迷宫的行，列
	for (i = 0; i < M + 2; i++)
	{
	mg[i][0] = 1;
	mg[i][M + 1] = 1;
	}
	for (i = 0; i < N + 2; i++)
	{
	mg[0][i] = 1;
	mg[M + 1][i] = 1;
	}
	for (i = 1; i < M + 1; i++)
	{
	for (j = 1; j < N + 1; j++)
	{
	cin >> mg[i][j];
	}
	}	//将迷宫初始化，在外围建立一堵墙
	SearchPath(1, 1, M, N);	//查找迷宫起点到终点是否有通路
	return 0;
}

运行结果如下：

2.关于用栈解决：

对于迷宫问题用栈解决主要基于栈的特性Fist in Last（先进后出），可以很好的存储走迷宫时的中间状态——经过的路径。根据先进后出的特点可以大概想到看先将走过的路径存入栈内，当路走不通时将栈中的该路径弹出。同时根据迷宫的特点我们想到用二维数组来储存我们的迷宫。那么大概的思路便是遍历迷宫中的路径，将路径存入栈内，当所在路径没有新的路可走时开始回退也就是将栈内的元素弹出直到栈顶元素可以找到新的路径。
根据大概的思路先来定义会使用到的数据结构。

（1）对于迷宫中位置的存储定义一个数据结构，基于我们是用二维数组来存储迷宫，那么可以采用横坐标和纵坐标来描述位置。同时遍历路径我们需要一个能反映当前方向的变量所以有以下定义：

typedef struct
{
 int x, y;
 int di;//按照东南西北的顺序，di从1-4.
}Box;

(2)根据用横纵坐标来存储位置信息，可以使用横坐标和纵坐标的增减来表示移动因此可以定义一个结构数组来表示增减量所以有以下定义：

typedef struct
{
 int x, y;//用x，y的增量来表示移动
}Direction;
Direction direct[5]{ {0,0},{1,0},{0,-1},{-1,0},{0,1} };//设定按东南西北的顺序来寻找出口

现在开始正式思考如何寻找迷宫的出口。首先找迷宫有两大步骤：1）在没路时能将栈内的元素弹出。2）能遍历迷宫能走的位置。那么我们可以设置双层循环嵌套，将遍历迷宫位置的步骤作为内层循环，弹出栈内元素作为外层循环。当遍历迷宫位置无路可走时退出内层循环进入外层循环将元素弹出直到有新的路径出现时。
同时对于走过的路径也应进行标记使系统能识别该位置走过，那么我们采用将走过的路的值赋为-1（用1表示迷宫的墙，0来表示可走的路）。
以下是代码的具体实现：

int findPath( int M,int N)
{
 Box temp;
 stack<Box> s;
 int x, y, di;//存储当前地点的横坐标和纵坐标
 int line, col;//存储下一个地点的横坐标和纵坐标
 Direction direct[5]{ {0,0},{1,0},{0,-1},{-1,0},{0,1} };//设定按东南西北的顺序来寻找出口
 mg[1][1] = -1;//将记过的地方设置为-1
 temp={ 1,1,0 };
 s.push(temp);//为循环同一先将入口存入栈内
 while (!s.empty())
 {
 temp = s.top();
 s.pop();
 x = temp.x;
 y = temp.y;
 di = temp.di + 1;
 while (di <= 4)//方向未尝试完
 {
 line = x + direct[di].x;//根据di的取值来进行相应方向的横纵坐标的增减
 col = y + direct[di].y;
 if (mg[line][col] == 0)
 {
 temp = { x,y,di };
 s.push(temp); //当有新路径时将上个位置存入栈内
 x = line;//表示移动到下一个地点
 y = col;
 mg[line][col] = -1;
 if (x == M && y == N) {//迷宫有路
 cout<< '(' << M << ',' << N << ')' << endl;
 while (!s.empty())
 {
 cout << '(' << s.top().x << ',' << s.top().y << ')' << endl;
 s.pop();
 }
 return 1;
 }
 else {
 di = 1;
 }
 }
 else {
 di++;
 }
 }
 }
 cout<<"迷宫没有出路";//返回0说明迷宫没有路
 return 0;
}

运行结果如下

总结：对于用栈和队列解决迷宫问题本质上是源于对栈和队列优点的利用，FIFO和FILO，基于此优点还可以解决更多同类问题如：查找文件指定名，对扑克牌排序和蜘蛛纸牌等，感兴趣的人也可去加以尝试，此后也将分享有关这方面的代码和知识，感谢阅览。