[数据结构与算法]栈解决迷宫求解问题

栈解决迷宫求解问题

标签（空格分隔）： 栈、回溯算法

一、引入

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

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

二、栈的特点

• 栈是一种线性表，只不过它是操作受限的线性 表，只能在一端操作。 进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储。下面代码中采用顺序存储实现栈。

• 栈的结构示意图：
  

其中，base 指向栈底，top 指向栈顶。 注意：栈只能在一端操作，后进先出，这是栈的关键特征，也就是说不允许在中间查找、取值、插入、删除等 操作。

三、具体实现

• 顺序栈的构建：
  这里将顺序栈的实现代码都写在头文件maze.h中，用于等下迷宫求解

#pragma once
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct _Position{//迷宫坐标
	int _x;
	int _y;
}Position;
#define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定
typedef Position ElemType;
typedef struct _SqStack{
	ElemType *base; //栈底指针
	ElemType *top; //栈顶指针
}SqStack;

bool InitStack(SqStack &S) //构造一个空栈 S
{
	S.base = new ElemType[MaxSize];//为顺序栈分配一个最大容量为 Maxsize的空间
	if (!S.base) //空间分配失败
		return false;
	S.top=S.base; //top 初始为 base，空栈
	return true;
}

bool PushStack(SqStack &S, ElemType e) // 插入元素 e 为新的栈顶元素
{

	if (S.top-S.base == MaxSize) //栈满
		return false;
	*(S.top++) = e; //元素 e 压入栈顶，然后栈顶指针加 1，等价于*S.top=e;S.top++;
	return true;
}

bool PopStack(SqStack &S, ElemType &e) //删除 S 的栈顶元素，暂存在变量 e中
{
	if (S.base == S.top){ //栈空
		return false;
	}
	e = *(--S.top); //栈顶指针减 1，将栈顶元素赋给 e
	return true;
}

ElemType* GetTop(SqStack &S) //返回 S 的栈顶元素，栈顶指针不变
{
	if (S.top != S.base){ //栈非空
		return S.top - 1; //返回栈顶元素的值，栈顶指针不变
	}else{
		return NULL;
	}
}

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

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

void DestoryStack(SqStack &S){//销毁栈
	if(S.base){

		free(S.base);
		S.base = NULL;
		S.top = NULL;
	}
}

• 迷宫求解路径部分代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "maze.h"
#include <assert.h>
#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)
		{
			printf("%d ",m->map[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int IsValidEnter(Maze* m, Position cur) //判断是否是有效的入口
{
	assert(m);
	if ((cur._x == 0 || cur._x == ROW - 1)
		|| (cur._y == 0 || cur._y == COL - 1)
		&& (m->map[cur._x][cur._y] == 1))
		return 1;
	else
		return 0;
}

int IsNextPass(Maze* m,Position cur, Position 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)))){//或在同一列上并且相邻
			//判断下一个节点是否在迷宫里面
			if (((next._x >= 0 && next._x < ROW) || (next._y >= 0 && next._y
				< COL))
				&&(m->map[next._x][next._y] == 1)){
					return 1;
			}
	}
	return 0;
}

int IsValidExit(Maze* m, Position cur,Position 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 1;
	}
	else
		return 0;
}
//核心代码：
int PassMaze(Maze* m,Position enter,SqStack* s) //找迷宫通路
{
	assert(m && IsValidEnter(m,enter) == 1); //对给的迷宫的入口进行合法性判断
	Position cur = enter;
	Position next;
	PushStack(*s, cur); //首先将迷宫的入口压入栈中
	m->map[cur._x][cur._y] = 2; //将入口值改为 2
	//PrintMaze(m);
	while (!IsEmpty(*s)) {
		cur = *GetTop(*s);
		//printf("cur: %d %d\n",cur._x, cur._y);
		if (IsValidExit(m,cur,enter) == 1) //判断当前位置是否出口
			return 1;
		//尝试向左一步：看当前节点的左一个节点能不能走通
		next = cur;
		next._y = cur._y - 1;
		if (IsNextPass(m, cur, next) == 1)
		{
			PushStack(*s, next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
			//PrintMaze(m);
			continue;
		}
		//尝试向上一步:看当前节点的上一个节点能不能走通
		next = cur;
		next._x = cur._x - 1;
		if (IsNextPass(m,cur,next) == 1) //next 节点能够走通时，将其压入栈中
		{
			PushStack(*s,next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y]+1; //将next 节点的值等于 cur 节点的值加 1
				//PrintMaze(m);
				continue;
		}
		//右：看当前节点的向右的一个节点能不能走通
		
		next = cur;
		next._y = cur._y + 1;
		if (IsNextPass(m, cur,next) == 1)
		{
			PushStack(*s, next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
			//PrintMaze(m);
			continue;
		}
		//下：看当前节点的下一个节点能不能走通
		next = cur;
		next._x = cur._x + 1;
		if (IsNextPass(m, cur,next) == 1)
		{
			PushStack(*s, next);
			m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
			//PrintMaze(m);
			continue;
		}
		//走到这里说明当前节点的四个方向都走不通，进行回溯，看前一个节点未被遍历的方向是否还能走通
		Position tmp;
		PopStack(*s, tmp);
	}
	return 0;
}

• 测试代码：

int main()
{
	int map[ROW][COL] = { //用二维数组描绘迷宫：1 代表通路，0 代表墙
		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;
	Position enter; //迷宫入口
	enter._x = 0;
	enter._y = 2;
	InitMaze(&m, map);
	PrintMaze(&m);

	SqStack s; //定义栈，保存已走过的坐标轨迹，便于回溯
	InitStack(s); //栈的初始
	int ret = PassMaze(&m,enter,&s); //使用栈和回溯法解开迷宫
	if(ret){
		printf("恭喜你！终于找到了出口~\n");
	}else {
		printf("不是我笨！实在没有出口~\n");
	}
	PrintMaze(&m);
	system("pause");
	return 0;
}

四、输出结果：

• 打印初始迷宫，1代表当前位置可以到达，0代表不可到达。
• 代码中将迷宫的入口地址（合法的入口地址情况下）设为2，将入口地址压栈，每个节点有四个方向可走，按照左、上、右、下的顺序遍历。都走不通的话回退到上一个位置，将栈顶元素出栈即可。
• 下一个位置在数组中的值是当前位置在数组中的值加1（回退的情况除外，只有在遍历未走过的位置才成立）。
  
  实际路径：2-3-4-5-4-3-4-5-6-5-6-7-8-9