递归和非递归解决迷宫问题

1、问题描述： 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 2、基本要求： （1）以链栈作为存储结构，编写一个求解迷宫的非递归程序，并将求得的通路以三元组（i,j,d）的形式输出，其中： i,j指示迷宫中的一个坐标，d表示走到下一坐标的方向； （2）编写递归形式的算法，求得迷宫中所有可能的通路； （3）以方阵形式输出迷宫及其通路。（选做） [测试数据] 左上角（1，1）为入口，右下角（9，8）为出口。

	#include
	#include 
	#include 
	#include
	#include   //函数状态码定义
	#define TRUE        1 
	#define FALSE       0 
	#define OK          1 
	#define ERROR       0 
	#define INFEASIBLE -1
	#define NULL       0 
	#define M   9   //行数
	#define N    8    //列数
	//墙或通路及前进方向符号定义
	#define WALL  1       //代表当前格子是墙
	#define PATH  0         //代表是通路且未走过 
	#define RIGHT -1        //代表是通路且从其向右走
	#define DOWN -2        //代表是通路且从其向下走 
	#define LEFT -3        //代表是通路且从其向左走
	#define UP   -4        //代表是通路且从其向上走 
	#define BACK -5        //代表是通路且从其后退一步
	#define DESTINATION -6  //代表当前格子是通路且是目标位置    
	typedef int MazeType[M + 2][N + 2]; //最外凿初始化成墙，实际含9*8个格子 
	typedef int Status;
	typedef int ElemType; //迷宫数组中的元素类型  

	/*-----------------------------------------------------------------------*/
	#define STACK_INIT_SIZE 100 
	#define STACKINCREMENT 10  
	typedef struct
	{
		int x;
		int y;
	}PosType;//迷宫中坐标的位置 
	typedef struct
	{
		int ord;
		PosType seat;
		int di;
	}SElemType;//栈中元素类型 
	typedef struct
	{
		SElemType *base;
		SElemType *top;
		int stacksize;
	}Stack;//栈类型 
	Status InitStack（Stack &S）
	{ //构造空栈S  
		S.base = （SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
		if （!S.base） exit（OVERFLOW）;    //存储分配失败 
		S.top = S.base;   //空栈
		S.stacksize = STACK_INIT_SIZE;
		return OK;
	}//InitStack 
	Status Push（Stack &S SElemType e）
	{ //插入e为栈顶元素  
		if （S.top - S.base >= S.stacksize）
			//栈满则应重新分配空间 
		{
			S.base = （SElemType *）realloc（S.base （S.stacksize + STACKINCREMENT）*sizeof（SElemType））;
			if （!S.base） exit（OVERFLOW）;
			S.top = （S.base + S.stacksize）;//使得S.top重新指向原栈顶因realloc 	
			S.stacksize += STACK_INIT_SIZE;
		}
		*S.top++ = e;  //top指向待插入位置   
		return OK;
	}//Push  
	Status Pop（Stack &S SElemType &e）
	{     //若栈不空则栈顶元素出栈并用e带回其值    
		if （S.top == S.base）
			return ERROR;
		else
			e = *（--S.top）;     //栈顶元素为*（S.top-1）   
		return OK;
	}
	Status GetTop（Stack S SElemType &e）
	{
		if （S.top == S.base）
			return ERROR;
		e = *（S.top - 1）;  //注意top指向待插入位置 
		return OK;
	}
	Status StackEmpty（Stack S）
	{//判空 	
		if （S.top == S.base）
			return TRUE;
		else
			return FALSE;
	}//StackEmpty 
	Status StackTraverse（Stack S Status（*visit）（SElemType））
	{ 	//从栈底元素到栈顶元素依次执行visit函数，通常用于输出栈中元素 	
		SElemType *p = S.base;
		if （S.base == S.top）
			printf（“空栈\n“）;
		else
			printf（“（1代表RIGHT2代表DOWN3代表LEFT4代表UP）\n“）;
		while （p		{
			（*visit）（*p）; ++p;
		}
		return OK;
	}
	Status PrintSElem（SElemType e）
	{
		printf（“step%d  : （%d%d%d）\n“ e.ord e.seat.x e.seat.y e.di）;
		return OK;
	}
	//迷宫求解的具体算法


	//输出初始迷宫
	void PrintMaze（MazeType &maze）
	{
		int x y;
		for （x = 0; x <= 10; x++）
		{
			for （y = 0; y <= 9; y++）
			{
				switch （maze[x][y]）
				{
				case WALL:printf（“■“）; break;
				case PATH:printf（“  “）; break;
				case RIGHT:printf（“→“）; break;
				case DOWN: printf（“↓“）; break;