#include
	#include?
	#include?
	#include
	#include???//函數(shù)狀態(tài)碼定義
	#define?TRUE????????1?
	#define?FALSE???????0?
	#define?OK??????????1?
	#define?ERROR???????0?
	#define?INFEASIBLE?-1
	#define?NULL???????0?
	#define?M???9???//行數(shù)
	#define?N????8????//列數(shù)
	//墻或通路及前進方向符號定義
	#define?WALL??1???????//代表當(dāng)前格子是墻
	#define?PATH??0?????????//代表是通路且未走過?
	#define?RIGHT?-1????????//代表是通路且從其向右走
	#define?DOWN?-2????????//代表是通路且從其向下走?
	#define?LEFT?-3????????//代表是通路且從其向左走
	#define?UP???-4????????//代表是通路且從其向上走?
	#define?BACK?-5????????//代表是通路且從其后退一步
	#define?DESTINATION?-6??//代表當(dāng)前格子是通路且是目標(biāo)位置????
	typedef?int?MazeType[M?+?2][N?+?2];?//最外鑿初始化成墻，實際含9*8個格子?
	typedef?int?Status;
	typedef?int?ElemType;?//迷宮數(shù)組中的元素類型??

	/*-----------------------------------------------------------------------*/
	#define?STACK_INIT_SIZE?100?
	#define?STACKINCREMENT?10??
	typedef?struct
	{
		int?x;
		int?y;
	}PosType;//迷宮中坐標(biāo)的位置?
	typedef?struct
	{
		int?ord;
		PosType?seat;
		int?di;
	}SElemType;//棧中元素類型?
	typedef?struct
	{
		SElemType?*base;
		SElemType?*top;
		int?stacksize;
	}Stack;//棧類型?
	Status?InitStack（Stack?&S）
	{?//構(gòu)造空棧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）
			//棧滿則應(yīng)重新分配空間?
		{
			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））
	{?	//從棧底元素到棧頂元素依次執(zhí)行visit函數(shù)，通常用于輸出棧中元素?	
		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;