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

#define xIndex 3
#define yIndex 3
#define TRUE 1
#define FALSE 0

int startIndX = 0;
int startIndY = 0;
int endIndX = 2;
int endIndY = 2;

// Structure to construct final path
typedef struct node {
	int x;
	int y;
	int parentVal;
} parent;

typedef struct queue {
    int x;
    int y;
    struct queue *next;
} qnode;

qnode *head;
qnode *tail;

// Neighbour index coordinates
int neighbourIndex[4][2];
int array[xIndex][yIndex];
int visited[xIndex][yIndex];
int row = xIndex - 1;
int col = yIndex - 1;
int startRow = 0;
int startCol = 0;

parent* parentArr[xIndex][yIndex];

// Function declarations
void neighbour(int sx, int sy);
int isVisited(int x, int y);
void markVisited(int x, int y);
void markUnvisited(int x, int y);
void markParent(int childX, int childY, int parentX, int parentY);
void findPath(int startX, int startY, int endX, int endY);
void enqueue(int x, int y);
qnode* dequeue();
int isQueueEmpty();
void printPath(int x, int y);
void freeQueue();
void test1();


void neighbour(int sx, int sy)
{
    int i = 0;
    int j = 0;

    for (i = 0; i < 4; i++) {
	for (j = 0; j < 2; j++) {
	    neighbourIndex[i][j] = -1;
	}
    }

    i = 0; j = 0;

    if (sy - 1 >= startCol && sy - 1 <= col) {
	neighbourIndex[i][0] = sx;
	neighbourIndex[i][1] = sy - 1;
	i++;
    }

    if (sx - 1 >= startRow && sx - 1 <= row) {
	neighbourIndex[i][0] = sx - 1;
	neighbourIndex[i][1] = sy;
	i++;
    }

    if (sy + 1 >= startCol && sy + 1 <= col) {
	neighbourIndex[i][0] = sx;
	neighbourIndex[i][1] = sy + 1;
	i++;
    }

    if (sx + 1 >= startRow && sx + 1 <= row) {
	neighbourIndex[i][0] = sx + 1;
	neighbourIndex[i][1] = sy;
	i++;
    }
}

int isVisited(int x, int y)
{
    return visited[x][y];
}

void markVisited(int x, int y)
{
    visited[x][y] = 1;
}

void markUnvisited(int x, int y)
{
    visited[x][y] = 0;
}

void markParent(int childX, int childY, int parentX, int parentY)
{
    parent* temp = (parent *)malloc(sizeof(parent));

    if (temp == NULL) {
	// Put ASSERT
    }

    temp->x = parentX;
    temp->y = parentY;
    temp->parentVal = array[parentX][parentY];

    parentArr[childX][childY] = temp;
}

void enqueue(int x, int y)
{
    qnode *temp = (qnode *)malloc(sizeof(qnode));
    if (temp == NULL) {
    // Put ASSERT
    }

    temp->x = x;
    temp->y = y;
    temp->next = NULL;

    tail->next = temp;

    tail = temp;
}

qnode* dequeue()
{
    qnode *temp;

    if (!isQueueEmpty()) {
        temp = head->next;
        head->next = temp->next;
        return temp;
    }

    return head->next;
}

int isQueueEmpty()
{
    if (head->next == NULL) {
        return TRUE;
    }

    return FALSE;
}

void freeQueue()
{
    qnode* temp;

    while (head->next != NULL) {
        temp = head->next;
        head->next = head->next->next;

        free (temp);
    }

}

void printPath(int x, int y)
{
    parent *pInfo;

    printf("Path:\n");
    while (1) {
        printf ("%d ", array[x][y]);

        pInfo = parentArr[x][y];
        x = pInfo->x;
        y = pInfo->y;

        if (x == startIndX && y == startIndY) {
            printf ("%d ", array[x][y]);
            break;
        }
    }
}

void findPath(int startX, int startY, int endX, int endY)
{
    int i = 0;
    int j = 0;
    int x = startX;
    int y = startY;
    int neighbourX = startX;
    int neighbourY = startY;
    int reached = FALSE;
    qnode *nextNode;


    while (1) {
        neighbour(x, y);

        // Check, are we neighbour of destination?
        for (i = 0; i < 4; i++) {
            if (neighbourIndex[i][0] == endX && neighbourIndex[i][1] == endY) {
                // Reached destination
                neighbourX = neighbourIndex[i][0];
                neighbourY = neighbourIndex[i][1];
                markParent(neighbourX, neighbourY, x, y);

                reached = TRUE;
                break;
            } else {
                // Validate neighbour
                if (neighbourIndex[i][0] != -1) {
                    neighbourX = neighbourIndex[i][0];
                    neighbourY = neighbourIndex[i][1];
                    if (array[x][y] < array[neighbourX][neighbourY]) {
                        // Mark neighbour index as visited
                        markVisited(x, y);
                        markVisited(neighbourX, neighbourY);

                        // Make me parent of neighbour index
                        markParent(neighbourX, neighbourY, x, y);

                        // Add neighbour to queue
                        enqueue(neighbourX, neighbourY);
                    }
                }
            }
        } // end of for

        if (reached) {
            // print path
            printPath(endIndX, endIndY);
            break;
        }

        if (isQueueEmpty()) {
            // If queue is empty then halt, no path found
            printf ("No valid path exist");
            break;
        }

        // Get next item from queue
        nextNode = dequeue();
        if (nextNode != NULL) {
            x = nextNode->x;
            y = nextNode->y;

            free (nextNode);
        }
    } // end of while
}


void test1()
{
    int i = 0;
    int j = 0;

    array[0][0] = 1;
    array[0][1] = 6;
    array[0][2] = 8;
    array[1][0] = 4;
    array[1][1] = 7;
    array[1][2] = 9;
    array[2][0] = 5;
    array[2][1] = 2;
    array[2][2] = 3;

    printf("\n\n");
    for (i = 0; i <= row; i++) {
        for (j = 0; j <= col; j++) {
            printf("%d   ", array[i][j]);
        }
        printf("\n");
    }

    findPath(startIndX, startIndY, endIndX, endIndY);
    freeQueue();
}

int main()
{
    head = (qnode*)malloc(sizeof(qnode));
    head->x = -1;
    head->y = -1;
    head->next = NULL;

    tail = head;

    test1();

    return 0;
}