//base.h
#include <stdio.h>
#include< iostream.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
 
//stack.h
//#include "base.h"
#define INIT_SIZE 100 //存儲空間初始分配量
#define INCREMENT 10  //存儲空間分配增量
typedef struct{       //迷宮中r行c列的位置
	int r;
	int c;
}PostType;
typedef struct{
	int ord;      //當前位置在路徑上的序號
	PostType seat;//當前坐標
	int di;       //往下一坐標的方向
}SElemType;        //棧元素類型
typedef struct{
	SElemType* base;//?；?構造前銷毀后為空
	SElemType* top;//棧頂
	int stackSize;  //棧容量
}Stack;             //棧類型
Status InitStack(Stack &S){	//構造空棧s
	S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
	if(!S.base)
		exit(OVERFLOW);//存儲分配失敗
	S.top=S.base;
	S.stackSize=INIT_SIZE;
	return OK;
}//InitStack
Status StackEmpty(Stack S){	
//若s為空返回TRUE,否則返回FALSE
	if(S.top==S.base)
		return TRUE;
	return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
 //插入元素e為新的棧頂元素
	if(S.top-S.base >=S.stackSize){//棧滿，加空間
		S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
		if(!S.base)
			exit(OVERFLOW);   //存儲分配失敗
		S.top=S.base+S.stackSize;
		S.stackSize+=INCREMENT;
	}
	*S.top++=e;
	return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若棧不空刪除棧//頂元素用e返回并返回OK，否則返回ERROR
	if(S.top==S.base)
		return ERROR;
	e=*--S.top;
	return OK;
}//Pop
Status DestroyStack(Stack &S){//銷毀棧S,
	free(S.base);
	S.top=S.base;
	return OK;
}//DestroyStack
 
//maze.cpp
//#include "stack.h"
#define MAXLEN 10//迷宮包括外墻最大行列數目
typedef struct{
	int r;
	int c;
	char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType;   //迷宮類型
Status InitMaze(MazeType &maze){
//初始化迷宮若成功返回TRUE,否則返回FALSE
	int m,n,i,j;
	cout<< "Enter row and column numbers: ";
	cin>>maze.r>>maze.c; //迷宮行和列數
	for(i=0;i<=maze.c+1;i++){//迷宮行外墻
		maze.adr[0][i]='#';
		maze.adr[maze.r+1][i]='#';
	}//for
	for(i=0;i<=maze.r+1;i++){//迷宮列外墻
		maze.adr[i][0]='#';
		maze.adr[i][maze.c+1]='#';
	}
	for(i=1;i<=maze.r;i++)
		for(j=1;j<=maze.c;j++)
			maze.adr[i][j]=' ';//初始化迷宮
	cout<<"Enter block's coordinate((-1,-1) to end): ";
	cin>>m>>n;//接收障礙的坐標
	while(m!=-1){
		if(m>maze.r || n>maze.c)//越界
			exit(ERROR);
		maze.adr[m][n]='#';//迷宮障礙用'#'標記
		cout<<"Enter block's coordinate((-1,-1) to end): ";
		cin>>m>>n;
	}//while
	return OK;
}//InitMaze	
Status Pass(MazeType maze,PostType curpos){
//當前位置可通則返回TURE,否則返回FALSE
	if(maze.adr[curpos.r][curpos.c]==' ')//可通
		return TRUE;
	else
		return FALSE;
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走過并且可通返回TRUE,否則返回FALSE
//在返回之前銷毀棧S
	maze.adr[curpos.r][curpos.c]='*';//"*"表示可通
	return OK;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐標
	PostType cpos;
	cpos=curpos;
	switch(i){        //1.2.3.4分別表示東,南,西,北方向
		case 1 : cpos.c+=1; break;
		case 2 : cpos.r+=1; break;
		case 3 : cpos.c-=1; break;
		case 4 : cpos.r-=1; break;
		default: exit(ERROR);	
	}
	return cpos;
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走過但不是通路標記并返回OK
	maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走過但不通
	return OK;
}//MarkPrint
Status MazePath(MazeType &maze,PostType start,PostType end){
	//若迷宮maze存在從入口start到end的通道則求得一條存放在棧中
	//并返回TRUE,否則返回FALSE
	Stack S;
	PostType curpos;
	int curstep;//當前序號,1.2.3.4分別表示東,南,西,北方向
	SElemType e;
	InitStack(S);
	curpos=start; //設置"當前位置"為"入口位置"
	curstep=1;   //探索第一步
	do{
		if(Pass(maze,curpos)){//當前位置可以通過,
//即是未曾走到過的通道
			FootPrint(maze,curpos);//留下足跡
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);              //加入路徑
			if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))//銷毀失敗
exit(OVERFLOW);
else 
	 return TRUE; //到達出口
			else{
				curpos=NextPos(curpos,1); 
//下一位置是當前位置的東鄰
				curstep++;       //探索下一步
			}//else
		}//if
		else{    //當前位置不通
			if(!StackEmpty(S)){
				Pop(S,e);
				    while(e.di==4
&& !StackEmpty(S)){
					MarkPrint(maze,e.seat);
					Pop(S,e);        
//留下不能通過的標記,并退一步
				}//while
				if(e.di < 4){
					e.di++;//換下一個方向探索
					Push(S,e);            
					curpos=NextPos(e.seat,e.di);//設定當前位置是該
//新方向上的相鄰
				}//if
			}//if
		}//else
	}while(!StackEmpty(S));
	if(!DestroyStack(S))//銷毀失敗
	   exit(OVERFLOW);	    
 else 
	   return FALSE;
}//MazePath
void PrintMaze(MazeType &maze){
//將標記路徑信息的迷宮輸出到終端(包括外墻)
	int i,j;
	cout<<"\nShow maze path(*---pathway):\n\n";
	cout<<"  ";
	for(i=0;i<=maze.r+1;i++)//打印列數名
		cout<<" "<<i;
	cout<<"\n"<<"\n";
	for(i=0;i<=maze.r+1;i++){
		cout<<" "<<i;//打印行名 
		for(j=0;j<=maze.c+1;j++)
	cout<<" "<<maze.adr[i][j];//輸出迷宮//當前位置的標記          
		cout<<"\n"<<"\n";
	}
}//PrintMaze
 
void main(){     //主函數
	MazeType maze;
	PostType start,end;
	char cmd;
	do{
		cout<<"-------FOUND A MAZEPATH--------\n";
		if(!InitMaze(maze)){  //初始化并創建迷宮
		cout<<"\nInitialization errors!!!\n";
			exit(OVERFLOW);     //初始化錯誤
		}
		do{                 //輸入迷宮入口坐標
			cout<<"\nEnter entrance coordinate of the maze: ";
			cin>>start.r>>start.c;
			if(start.r>maze.r || start.c>maze.c){
				cout<<"\nBeyond the maze!!!\n";
				continue;
			}
		}while(start.r>maze.r || start.c>maze.c);
		do{                 //輸入迷宮出口坐標
			cout<<"\nEnter exit coordinate of the maze: ";
			cin>>end.r>>end.c;
			if(end.r>maze.r || end.c>maze.c){
				cout<<"\nBeyond the maze!!!\n";
				continue;
			}
		}while(end.r>maze.r || end.c>maze.c);
		if(!MazePath(maze,start,end))//迷宮求解
			cout<<"\nNo path from entrance to exit!\n";
		else
			PrintMaze(maze);//打印路徑
	cout<<"\nContinue?(y/n): ";
		cin>>cmd;
	}while(cmd=='y' || cmd=='Y');
}//main