#define MAXNUM        100
#define N 12
#include <stdio.h>
#include <stdlib.h>

typedef struct

{

int  x;

int  y;

int  d;

}DataType;

	struct  SeqStack	  		
	{	DataType  s[MAXNUM];
		int  t; 			
	};
	typedef  struct SeqStack  *PSeqStack;	
	PSeqStack  pastack;					


PSeqStack  createEmptyStack_seq( void )
   {  PSeqStack pastack;
	  pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
	  if (pastack==NULL)
			printf("Out of space!! \n");
	  else
			pastack->t=-1;
	  return  (pastack);
}


int  isEmptyStack_seq( PSeqStack pastack )
    {
	    return ( pastack->t == -1 );
}


void  push_seq( PSeqStack pastack, DataType x )

{  if( pastack->t >= MAXNUM - 1  )
      printf( "Overflow! \n" );
  else
	{  pastack->t = pastack->t + 1;
	   pastack->s[pastack->t] = x;
	 }
}


void  pop_seq( PSeqStack pastack )

{  	if (pastack->t == -1 )
			printf( "Underflow!\n" );
    		else
			pastack->t = pastack->t - 1;
	}


DataType  top_seq( PSeqStack pastack )

    {
        return (pastack->s[pastack->t]);
	 }



void pushtostack(PSeqStack st, int x, int y, int d)

{    DataType element;

      element.x = x;

element.y = y;

element.d = d;

push_seq(st,element);

}



void printpath(PSeqStack st)

{DataType element;
printf("                                        The revers path is:\n");
printf("--------------------------------------------------------------------------------\n");

while(!isEmptyStack_seq(st))

{    element=top_seq(st);

pop_seq(st);

printf("the node is: %d %d \n",element.x,element.y);

}

}




void mazePath(int maze[][N],int direction[][2],int x1,int y1,int x2,int y2)


{    int i,j,k,g,h;

PSeqStack st;

DataType element;

st = createEmptyStack_seq( );

maze[x1][y1] = 2;                                       

pushtostack(st, x1, y1, -1);            

while (! isEmptyStack_seq(st))        

{    element = top_seq(st);

pop_seq(st);

i = element.x; j = element.y; k = element.d + 1;

while (k<=3)                     

{    g = i + direction[k][0];h = j + direction[k][1];

if (g==x2 && h==y2 && maze[g][h]==0)     

{    printpath(st);       

return;

}

if (maze[g][h]==0)           

{    maze[g][h] = 2;         

pushtostack(st, i, j, k);   

i = g; j = h; k = -1;         

}

k = k + 1;

}

}

printf("The path has not been found.\n"); 

}

int main(){
int direction[][2]={0,1,1,0,0,-1,-1,0};
int maze[][N]={
1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,1,1,0,1,0,1,0,1,
1,1,1,0,1,0,0,0,0,0,0,1,
1,1,0,0,0,0,1,1,1,1,0,1,
1,1,0,1,1,1,1,1,1,1,0,0,
1,1,0,1,0,1,1,1,1,1,1,1,
1,1,0,0,0,1,1,1,1,1,1,1,
1,1,1,1,0,1,1,1,0,1,0,1,
1,1,0,0,0,0,0,1,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1
};
printf("--------------------------------------------------------------------------------\n");
printf("                                        the maze is\n");
printf("--------------------------------------------------------------------------------\n");
for(int i=0;i<=(N-1);i++)
{
	for(int j=0;j<=(N-1);j++)
	{
		if(maze[i][j]==1)
		{
			printf("#");
		}
		else
		{printf(".");}
 
	}
	printf("\n");
}
printf("--------------------------------------------------------------------------------\n");
printf("--------------------------------------------------------------------------------\n");
mazePath(maze,direction,8,2,4,11);
return 0;
}