#include<stdio.h>
#include<malloc.h>

int Maze[6][6]={1,1,1,1,1,1,1,0,1,0,1,1,1,0,0,0,1,1,1,0,0,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1};

typedef struct{
	int x;
	int y;
	int di;
}postype;

typedef struct{
	postype *base;
	postype *top;
	int stacksize;
}Sqstack;

void Set(postype &a,postype b){
	a.x=b.x;
	a.y=b.y;
	a.di=b.di;
}//賦值函數

void Initstack(Sqstack &s){
	s.base=(postype*)malloc(20*sizeof(postype));
	s.top=s.base;
	s.stacksize=20;
}//Initstack

void Pop(Sqstack s,postype &e){
	if(s.top!=s.base) {
		s.top--;
		e.di=s.top->di;   
		e.x=s.top->x;    e.y=s.top->y;
	}
}//Pop

void Push(Sqstack s,postype e){
	s.top->di=e.di;     
	s.top->x=e.x;    s.top->y=e.y;
	s.top++;
}//Push
 
int Stackempty(Sqstack s){
	return(s.top!=s.base);
}//判斷棧是否空，是則返回0

void Nextpos(postype &s,int di){
	switch(di){
	case 1:  s.x++; break;
	case 2:  s.y++; break;
	case 3:  s.x--; break;
	case 4:  s.y--; break;
	}
	s.di=di;
}//取下一個通道塊

void Mazepath(postype start,postype end){
	Sqstack s;  
	postype curpos,e;
	Set(curpos,start);//將start作為當前位置
	Initstack(s);
	do{
		if(!Maze[curpos.x][curpos.y]){
			Push(s,curpos);	printf("(%d,%d)",curpos.x,curpos.y); 
			Set(e,curpos);
			Maze[curpos.x][curpos.y]=1;
			if(curpos.x==4&&curpos.y==4)  break;
			else{
				Nextpos(curpos,1);  
			}
		}
		else{
			if(!Stackempty(s)){
				Pop(s,e);  
				while(e.di==4&&!Stackempty(s)){
					Maze[e.x][e.y]=-1;
					Pop(s,e);    
				}
				if(e.di<4){
					e.di++;   
					Push(s,e);
					Set(curpos,e);
					Nextpos(curpos,curpos.di);
				}
			}
		}
	}while(!Stackempty(s));
	while(!Stackempty(s)){
		Pop(s,curpos);
		printf("(%d,%d)",curpos.x,curpos.y);
	}
	
}//迷宮路徑函數

void main(){
	postype  start,end;
	start.x=1;   start.y=1;
	end.x=6;     end.y=6;
	printf("迷宮路徑如下：\n");
	Mazepath(start,end);
}//main