#include "maze_solver.h"
#include <string.h>
#include "utilities.h"

struct solver_data
{
    struct maze *maze;
    struct point *first_point;
    struct point *last_point;
    int count;
    //int temp[51][51];
    int **temp;
};

static void get_neighbours(struct point point, struct point *neighbours)
{
    neighbours[0].x = point.x + 1;
    neighbours[0].y = point.y;
    neighbours[1].x = point.x - 1;
    neighbours[1].y = point.y;
    neighbours[2].x = point.x;
    neighbours[2].y = point.y + 1;
    neighbours[3].x = point.x;
    neighbours[3].y = point.y - 1;
}

static int solve_maze_rec(struct solver_data *data, struct point point)
{
    if (data->first_point == NULL)
        data->count++;
    else
        *(data->last_point++) = point;

    data->temp[point.x][point.y] = 1;
    if (data->maze->end_point.x == point.x && data->maze->end_point.y == point.y)
    {
        if (data->first_point == NULL)
            return data->count;
        else
            return (data->last_point - data->first_point);
    }
    struct point neighbours[4];
    get_neighbours(point, neighbours);
    for (int i = 0; i < 4; i++)
    {
        if (neighbours[i].x >= 0 &&
            neighbours[i].y >= 0 &&
            neighbours[i].x < data->maze->width &&
            neighbours[i].y < data->maze->height &&
            data->maze->map[neighbours[i].x][neighbours[i].y] != 1 &&
            data->temp[neighbours[i].x][neighbours[i].y] != 1)
        {
            int value = solve_maze_rec(data, neighbours[i]);
            if (value >= 0)
                return value;
        }
    }
    if (data->first_point == NULL)
        data->count--;
    else
        data->last_point--;
    return -1;
}

int solve_maze(struct maze *maze, struct point point, struct point *path)
{
    struct solver_data solver_data;
    solver_data.maze = maze;
    solver_data.first_point = path;
    solver_data.last_point = path;
    solver_data.count = 0;
    int length = sizeof_2d(maze->width, maze->height, sizeof(int));
    char mem[length];
    memset(mem, 0, length);
    init2d((void **)mem, maze->width, maze->height, sizeof(int));
    solver_data.temp = (int **)mem;
    return solve_maze_rec(&solver_data, point) - 1;
}