资源简介

数据结构课程设计之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

评论

共有 条评论