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

#define MAX_STACK_SIZE 1000
#define MAX_SIZE 6

typedef struct {
    short r;
    short c;
} element;

typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;

void init(StackType *s)
{
    s->top = -1;
}

/**
 * \brief return the true if its empty.
 */
bool is_empty(StackType *s)
{
    if(s->top == -1) {
        return true;
    }
    
    return false;
}

/**
 * \brief return the true if its full.
 */
bool is_full(StackType *s)
{
    if(s->top == (MAX_STACK_SIZE - 1)) {
        return true;
    }
    
    return false;
}

/**
 * \brief push the element to the stack.
 */
void push(StackType *s, element item)
{
    int ret;
    
    ret = is_full(s);
    if(ret == true) {
        fprintf(stderr, "stack is full.\n");
        return;
    }
    
    s->top++;
    s->stack[s->top] = item;    
}

/**
 * \brief pop the element.
 */
element pop(StackType *s)
{
    int ret;
    element tmp_element;
    
    ret = is_empty(s);
    if(ret == true) {
        fprintf(stderr, "stack is empty\n");
        exit(1);
    }
    
    tmp_element = s->stack[s->top];
    s->top--;

    return tmp_element;
}

element peek(StackType *s)
{
    if (is_empty(s) == 1) {
        fprintf(stderr, "stack is empty");
        exit(1);
    }
    
    return s->stack[s->top];
}

element here = { 1,0 }; //here.r = 1, here.c = 0
element entry = { 1,0 }; //end.r =1 end.c = 0
char maze[MAX_SIZE][MAX_SIZE] = {
 {'1', '1', '1', '1', '1', '1'},
 {'e', '0', '1', '0', '0', '1'},
 {'1', '0', '0', '0', '1', '1'},
 {'1', '0', '1', '0', '1', '1'},
 {'1', '0', '1', '0', '0', 'x'},
 {'1', '1', '1', '1', '1', '1'},
};

void push_loc(StackType *s, int r, int c)
{
    if (r < 0 || c < 0) {
        return;
    }
    
    if ((maze[r][c] != '1') && (maze[r][c] != '.')) {
        element tmp;
        tmp.r = r;
        tmp.c = c;
        push(s, tmp);
    }
}

int main(){
    int r, c;
    StackType s;
    
    init(&s);
    here = entry;

    while(maze[here.r][here.c] != 'x') {
        r = here.r;
        c = here.c;
        
        maze[r][c] = '.';
        printf("Current location. r[%d], c[%d]\n", r, c);
                 
        push_loc(&s, r - 1, c);

        push_loc(&s, r + 1, c);

        push_loc(&s, r, c - 1);

        push_loc(&s, r, c + 1);

        
        if (is_empty(&s)) {
            printf("not exitn");
            return 1;
        }
        else {
            here = pop(&s);
        }
    }
    printf("success");
     
    return 0;
}