数据结构 迷宫问题 C++ 栈方法

数据结构课程设计之C++编写的迷宫问题路径求解程序，使用的是栈方法，即将路径上每一步存在栈中，迷宫文件格式见程序提示，压缩包内已经给出了三个测试用的迷宫地图可用来测试，支持分步显示查找路径过程功能，当给出的迷宫是死迷宫时会提示用户。注：压缩包是个DevC++项目，如需VC编译请把.cpp和.h文件提取出来建立项目。

//迷宫问题
//作者：金航161530115
//完成日期：2016-12-23
#include 
#include 
#include 
#include 
#include 
#include 
#include “MazeStack.h“

#define MAXWIDTH 50

using namespace std;

int maze[MAXWIDTH][MAXWIDTH];
MazeStack stk;
struct tagMazeinfo
{
	int m;		//行数
	int n;		//列数
	int x1 y1;	//起点坐标
	int x2 y2; //终点坐标 
} MI;
bool StepShow;

void LoadMaze（const char filename[]）;
void PrintMaze（bool StepShow）;
bool IsThisStepAva（Node &pt Node lastpt const int cmd）;
#define ASKAVA 1
#define GOINTO 2
void Pause（const char *say）;
bool JudgeDest（Node &curpt）;

int main（）
{
	char filename[100];
	Node curpt lastpt;
	bool flag = false;
	
	cout << “迷宫问题\n“
		 << “迷宫存在文件中，文件格式如下：\n“
		 << “第一行为行数m 列数n（含最外层边界）\n“
		 << “现约定以整个文件第四行第一个数为坐标（0 0），向右为x正方向，向下为y正方向\n“
		 << “第二行为起点坐标y1 x1\n“
		 << “第三行为终点坐标y2 x2\n“
		 << “接下来给出m行n列的地图\n“
		 << “地图中数字的代表说明\n“
		 << “0-可步入的坐标\n1-障碍物\n2-探索路径\n3-当前位置\n“
		 << “数据限制：\n3<=m<=50 3<=n<=50 1<=y1<=m-2 1<=x1<=n-2 1<=y2<=m-2 1<=x2<=n-2\n“
		 << “y1-y2+x1-x2!=0 array[y1][x1]!=1 array[y2][x2]!=1\n“
		 << “请输入文件名：\n>“;
	cin >> filename;
	LoadMaze（filename）;
	if （ERROR == stk.InitStack（））
	{
		cout << “栈初始化失败。“;
		Pause（“按任意键退出. . .“）;
		exit（1）;
	}
	curpt.horPos = 1;
	curpt.verPos = 1;
	curpt.under = NULL;
	maze[curpt.horPos][curpt.verPos] = CURPOS;
	if （StepShow）
	{
		stk.ShowAllStack（）;
	}
	PrintMaze（true）;
	Pause（NULL）;
	cout << “\n\n\n“;
	
	while （true）
	{
		GOAHEADLOOP:
		flag = false;	
		for （curpt.heading = RIGHT;
			 curpt.heading <= UP;
			 curpt.heading++）
		{
			if （IsThisStepAva（curpt lastpt ASKAVA））
			{
				
				stk.GetTop（lastpt）;
				if （curpt.heading == （lastpt.heading + 2）
					|| curpt.heading == （lastpt.heading - 2））
				{
					continue;
				}
				IsThisStepAva（curpt lastpt GOINTO）;
				PrintMaze（StepShow）;
				if （JudgeDest（curpt））
				{
					goto PROGRAMEND;
				}
				Pause（NULL）;
//				cout << “\n\n\n“;
				flag = true;
				break;
			}	
		}//End of GOAHEADLOOP
		
		GOBACKLOOP:
		if （!flag && !stk.IsStackEmpty（））
		{
			while （true）
			{
				stk.NodeCopy（lastpt curpt）;
				maze[curpt.horPos][curpt.verPos] = UNSTEPED;
				stk.Pop（curpt）;
				maze[curpt.horPos][curpt.verPos] = CURPOS;
				if （StepShow）
				{
					stk.ShowAllStack（）;
				}
				PrintMaze（StepShow）;					
				if （stk.IsStackEmpty（）
					&& curpt.horPos == MI.y1
					&& curpt.verPos == MI.x1
					&& curpt.heading >= UP） 	 
				{
					cout << “此迷宫无解。\n“;
					goto PROGRAMEND;
				}
				Pause（NULL）;
//				cout << “\n\n\n“;
				for （curpt.heading = curpt.heading;
					 curpt.heading <= UP;
					 curpt.heading++）
				{
					if （IsThisStepAva（curpt lastpt ASKAVA））
					{
						IsThisStepAva（curpt lastpt GOINTO）;
						PrintMaze（StepShow）;
						if （JudgeDest（curpt））
						{
							goto PROGRAMEND;
						}
						Pause（NULL）;
//						cout << “\n\n\n“;
						goto GOAHEAD

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-01-30 18:19  迷宫问题（栈）\
     文件        1301  2017-01-05 12:15  迷宫问题（栈）\Makefile.win
     文件        1727  2016-08-09 12:53  迷宫问题（栈）\MazeStack.cpp
     文件         918  2016-12-23 23:29  迷宫问题（栈）\MazeStack.h
     文件       69363  2017-01-05 12:15  迷宫问题（栈）\MazeStack.o
     文件         551  2017-01-05 16:46  迷宫问题（栈）\m.txt
     文件         373  2017-01-03 00:09  迷宫问题（栈）\m1.txt
     文件         609  2017-01-03 00:28  迷宫问题（栈）\m2.txt
     文件        6052  2017-01-03 00:29  迷宫问题（栈）\main.cpp
     文件       77707  2017-01-05 12:15  迷宫问题（栈）\main.o
     文件        1148  2017-01-03 04:49  迷宫问题（栈）\迷宫问题.dev
     文件     1992355  2017-01-05 12:15  迷宫问题（栈）\迷宫问题.exe
     文件         227  2018-01-30 18:19  迷宫问题（栈）\迷宫问题.layout