迷宫与栈问题（C++实现）

【问题描述】

以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【任务要求】

1) 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。

2) 编写递归形式的算法，求得迷宫中所有可能的通路。

3) 以方阵形式输出迷宫及其通路。

【测试数据】

迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）

 【需求分析】

分解迷宫与栈程序功能，具体描述每个程序中功能模板的内容，给出实现每个功模板对应的系统模块。迷宫问题一般是用“穷举求解”措施解决，即从入口出发，顺着某一种方向进行摸索，若能走通，则继续往前走否则沿着原路退回，换一种方向继续摸索，直至出口位置，求得一条通路。如果所有也许的通路都摸索到而未能达到出口，则所设定的迷宫没有通路。栈是一种后进先出的构造，可以用来保存从入口到目前位置的途径。

1.迷宫产生的方式
       定义迷宫类型来存储迷宫数据，一般设定入口点的下标为(1，1)，出口点的下标为(n，n)。为解决以便起见，在迷宫的四周加一圈障碍。对于迷宫任何一种位置，均定义为东、南、西、北四个方向可通。该程序设计是迷宫求解问题，首先初始化入口和出口的通路。程序先采用栈作为数据的逻辑结构。并且以链表作为存储构造栈的类型，用入栈出栈等判断栈是否为空等功能。以设计多功能求解迷宫问题，使用程序时有更多选择求解迷宫。

2.手动输入迷宫

      手动输入迷宫可以更好的加深对程序的理解，依次输入迷宫的行数和列数以及内墙的个数，运用递归算法，以三元组的形式输出从起点到终点的一条路径，再求解从起点到终点之间所有的路径，并以方阵的形式输出迷宫和通路，锻炼对代码的理解能力，使迷宫与栈问题功能能更加完善。

3.从文件读入迷宫

    利用文件读入迷宫是较为方便的方法之一，结合c语言与数据结构逻辑算法。构造一些文件操作，比如打开文件，扫描文件，获取文件数据等，加固对c语言的印象，提高操作能力。提前建好文件，输入指令可以扫描到文件的迷宫，用于求解迷宫是最为方便不过，还可以利用迷宫文件互相交流，效率显著提高。

1. 使用模板迷宫

    提前设定好迷宫模板，进行迷宫求解问题，不需要手动输入和以文件形式打开，提高求解效率，结合递归算法，利用函数判断是否起点合法，最后结合设定好的模板迷宫example[6][6]，完成迷宫路径求解，丰富程序功能运行，使用更为方便。

 【完整代码】

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include<windows.h>
#define M 60 
#define N 60 
#define END N-2
#define MAXLENGTH  60 // 设迷宫的最大行列为25
const int mERROR = 0;
const int OK = 1;
const int mFALSE = 0;
const int mTRUE = 1;
const int STACK_INIT_SIZE = 100;
const int STACKINCREMENT = 10;

int curstep = 2; // 当前足迹,设置初值为2，与0，1相区别 

typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 迷宫数组[行][列]
MazeType m;                                 //声明一个全局变量迷宫m
typedef int Status;
int flag=0;

int maze[M][N];//递归算法所使用的迷宫 
int route[M][N];//通路
typedef struct
{//递归法：位置结构体
   int X;
   int Y;
} PosType;
PosType mazeout;//迷宫出口 

typedef struct
{//三元组结构体，用于记录行走坐标和方位 
    int x;
	int y;
    int d;//用来标记方位
}position;

typedef struct triad_step{
	position triadstep[1024];
	int stepnum;
}TriadStep;
TriadStep mTriadStep;

typedef struct
{
   int ord;      //通道块在路径上的“序号”
   PosType seat; //通道块在迷宫中的“坐标位置”
   int di;       //从此通道块走向下一通道块的“方向”
} SElemType;     //栈的元素类型
typedef struct
{
   SElemType *base;
   SElemType *top;
   int stacksize;
} Stack;
int example[6][6] ={
    {1,1,1,1,1,1},
    {1,0,0,1,0,1},
    {1,0,0,1,0,1},
    {1,0,0,0,0,1},
    {1,0,1,1,0,1},
    {1,1,1,1,1,1},
};


/**********************************/
/* 输出迷宫图，0表示墙，1表示通路*/
/********************************/
void Print(int x, int y) 
{
   int i, j;
   for (i = 0; i < x; i++)
   {
      for (j = 0; j < y; j++)
      {
      	if(m[i][j]>1)
      	{
      	   printf("*");	
		}
		else 
		{		
		 printf("%d", m[i][j]);
     	}
      }
      printf("\n");
   }
}


/**********************************/
/*      三元组方式输出路径       */
/********************************/
void printtriadStep()
{
    int i;
	for(i=0;i<mTriadStep.stepnum-1;i++) 
	{
		printf("(%d,%d,%d)->", mTriadStep.triadstep[i].x,mTriadStep.triadstep[i].y,mTriadStep.triadstep[i].d);		
	}
	printf("(%d,%d,%d)", mTriadStep.triadstep[i].x,mTriadStep.triadstep[i].y,mTriadStep.triadstep[i].d);	
}


/**********************************/
/*        构造一个空栈S          */
/********************************/
Status InitStack(Stack *S)