#include<stdio.h>
#include<stdlib.h>


#define MAX_STACK 100
#define FALSE 0
#define TRUE 1


typedef struct{
    short int row;
    short int col;
    short int dir;
    }elements;

elements stack[MAX_STACK];
int top;

typedef struct{
    short int vert;
    short int horiz;
    }offsets;
offsets move[8];

int EXIT_COL, EXIT_ROW;
int **maze;
int mark[MAX_STACK][MAX_STACK];


void clear();
void Input_Direct();
void delet(int *top);
void add(int *top, elements item);
void path();


void main()
{
    int i, j;
       int max_col, max_row;
    EXIT_COL = 8;
    EXIT_ROW = 8;
    max_col = EXIT_COL + 2;
       max_row = EXIT_ROW + 2;
    maze = (int **)calloc(max_col, sizeof(int *));
    for( i= 0 ; i < max_col ; i++)
    maze[i] = (int *)calloc(max_row, sizeof(int));
   
    int maze[10][10] =
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
          1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
          1, 1, 0, 0, 1, 1, 1, 1, 1, 1,
          1, 1, 1, 0, 1, 1, 1, 0, 0, 1,
          1, 0, 0, 0, 0, 1, 0, 1, 1, 1,
          1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
          1, 0, 1, 1, 0, 0, 0, 0, 1, 1,
          1, 1, 1, 0, 0, 1, 1, 0, 1, 1,
          1, 1, 0, 0, 1, 1, 1, 0, 0, 1,
          1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

    for( i = 0 ; i < max_col ; i++)
    {
        for( j = 0 ; j < max_row ; j++)
        {
            mark[i][j] = 0 ;
        }
    }

    Input_Direct();
    clear();
    path();
}


void Input_Direct()
{
    move[0].vert=-1; move[0].horiz=0;
    move[1].vert=-1; move[1].horiz=1;
    move[2].vert=0; move[2].horiz=1;
    move[3].vert=1; move[3].horiz=1;
    move[4].vert=1; move[4].horiz=0;
    move[5].vert=1; move[5].horiz=-1;
    move[6].vert=0; move[6].horiz=-1;
    move[7].vert=-1; move[7].horiz=-1;
}


void clear()
{
    int i = 0;
    for( i = 0 ; i < MAX_STACK ; i++)
    *top[i] = NULL;
}


void push(int top, elements item)
{
    top++;
    stack[top] = item;
}



void pop(int top)
{      top--;
    return stack[top];
}

   


void path(void)
{
int i, row, col, next_row, next_col, dir, found=FALSE;
elements position;
mark[1][1]=1; top=0;
stack[0].row=1; stack[0].col=1; stack[0].dir=1;

while(top>-1 && !found){
    position = pop(*top);
    row = position.row;
    col = position.col;
    dir = position.dir;

    while(dir<8 && !found){
    next_row = row + move[dir].vert;
    next_col = col + move[dir].horiz;

    if(next_row==EXIT_ROW && next_col==EXIT_COL)
    found = TRUE;
    else if(!maze[next_row][next_col] && !mark[next_row][next_col])
    {
       mark[next_row][next_col] =1;
    position.row = row; position.col = col; position.dir = ++dir;
    add(&top, position);
    row = next_row; col = next_col; dir = 0;
    }
    else ++dir;
    }
    }

if(found){
    printf("THE PATH IS : \n");
    printf("ROW    COL\n");
    for(i = 0 ; i <= top ; i++)
        printf("%2d %5d\n", stack[i].row, stack[i].col);

    printf("%2d %5d\n", row, col);
    printf("%2d %5d\n", EXIT_ROW, EXIT_COL);
}
else printf("THIS MAZE IS BLOCKED PATH\n");
}