#include <iostream.h>
#include <stdlib.h>


#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define dim_x 12
#define dim_y 12

typedef int status;
typedef char MazeType[dim_x][dim_y];
 

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct {
	int x;
	int y;
}PosType;

typedef struct {
	PosType seat;
	int di;
}SElemType;

typedef struct
{ SElemType *base;
  SElemType *top;
  int stacksize;
}SqStack;

status InitStack(SqStack &S)
{ S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  if(!S.base) return OVERFLOW;
  S.top=S.base;
  S.stacksize=STACK_INIT_SIZE;
  return OK;
}

status StackEmpty(SqStack S)
{ if(S.top==S.base) return OK;
  else return FALSE;
}

status Push(SqStack &S, SElemType e)
{ if(S.top-S.base>=S.stacksize) {
	S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
    if(!S.base) return OVERFLOW;
    for(int i=0;i<S.stacksize;i++)
    *(S.base+i)=*(S.top-S.stacksize+i);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;  }
    *S.top++=e;
  return OK;
}

status Pop(SqStack &S, SElemType &e)
{ if(S.top==S.base) return ERROR;
  e=*--S.top;
  return OK;
}



status Pass(MazeType maz,PosType cur){
    if (maz[cur.x][cur.y]=='X'||maz[cur.x][cur.y]=='#'||maz[cur.x][cur.y]=='*') return FALSE;
	else return TRUE;
}

status FootPrint(MazeType maz,PosType cur){
	maz[cur.x][cur.y]='*';
	return OK;
}
 
PosType NextPos(PosType cur,int dir){
	PosType temp;
	switch(dir) {
	case 1: temp.x=cur.x;     temp.y=cur.y+1; break;
    case 2: temp.x=cur.x+1;   temp.y=cur.y; break;
    case 3: temp.x=cur.x;     temp.y=cur.y-1; break;
    case 4: temp.x=cur.x-1;   temp.y=cur.y; break;
	}
	return temp;
}

status MarkPrint(MazeType maz,PosType cur) {
	maz[cur.x][cur.y]='X';
	return OK;
}

status MazePath(MazeType maze,PosType start,PosType end){
	SqStack S;
	PosType curpos;
	SElemType e;
	InitStack(S);
	curpos=start;
	do{
		if(Pass(maze,curpos)){
			FootPrint(maze,curpos);
			e.seat=curpos; e.di=1;
			Push(S,e);
			if(curpos.x==end.x&&curpos.y==end.y) return TRUE;
			curpos=NextPos(curpos,1);
		}
		else {
			if(!StackEmpty(S)) {
				Pop(S,e);
				while(e.di==4&&!StackEmpty(S)) {
					MarkPrint(maze,e.seat); Pop(S,e);
				}
				if(e.di<4) {
					e.di++; Push(S,e);
					curpos=NextPos(e.seat,e.di);
				}
			}
		}
	}while(!StackEmpty(S));
	return FALSE;
}

status PrintMaze(MazeType maz,int dimx,int dimy) {
	for(int i=0;i<dimx;i++) {
	    for(int j=0;j<dimy;j++)
			cout<<maz[i][j];
			cout<<endl;
	}
	return OK;
}


int main()
{  MazeType maze={{'#','#','#','#','#','#','#','#','#','#','#','#'}
                 ,{'#','.','.','.','#','.','.','.','.','.','.','#'}
		 ,{'.','.','#','.','#','.','#','#','#','#','.','#'}
                 ,{'#','#','#','.','#','.','.','.','.','#','.','#'}
                 ,{'#','.','.','.','.','#','#','#','.','#','.','.'}
		 ,{'#','#','#','#','.','#','.','#','.','#','.','#'}
		 ,{'#','.','.','#','.','#','.','#','.','#','.','#'}
		 ,{'#','#','.','#','.','#','.','#','.','#','.','#'}
		 ,{'#','.','.','.','.','.','.','.','.','#','.','#'}
		 ,{'#','#','#','#','#','#','.','#','#','#','.','#'}
		 ,{'#','.','.','.','.','.','.','#','.','.','.','#'}
		 ,{'#','#','#','#','#','#','#','#','#','#','#','#'}};

   PosType entr,exit;
   entr.x=2; entr.y=0;
   exit.x=4; exit.y=11;
   cout<<"源迷宮圖:"<<endl;
   PrintMaze(maze,dim_x,dim_y);
   if(!MazePath(maze,entr,exit))
   {  cout<<"該迷宮沒有一條路徑.";
      return ERROR;
	  }
   cout<<"求解路徑后的迷宮:"<<endl;
   PrintMaze(maze,dim_x,dim_y);
   return OK;
}