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

//-----------------------------
typedef struct __tag_data
{
    int x, y;
} ElemType;

ElemType elem_next(ElemType *data, int direction)
{
    ElemType new = *data;

    if (1 == direction) new.x = new.x - 1;
    if (2 == direction) new.y = new.y - 1;
    if (3 == direction) new.y = new.y + 1;
    if (4 == direction) new.x = new.x + 1;

    return new;
}

//-----------------------------
typedef struct __tag_stack
{
    ElemType data;
    struct __tag_stack *next;
} StackNode, *Stack;

Stack stack_create()
{
    Stack stack = malloc(sizeof(StackNode));
    stack->next = NULL;

    return stack;
}

bool stack_empty(Stack stack)
{
    return stack->next == NULL;
}

StackNode stack_top(Stack stack)
{
    if (stack_empty(stack))
    {
        perror("stack empty");
        exit(EXIT_FAILURE);
    }
    return *stack->next;
}

void stack_push(Stack stack, ElemType elem)
{
    Stack p = malloc(sizeof(StackNode));
    p->data = elem;

    p->next = stack->next;
    stack->next = p;
}

void stack_pop(Stack stack, ElemType *elem)
{
    Stack p = stack->next;
    stack->next = p->next;
    *elem = p->data;

    free(p);
}

void stack_destroy(Stack stack)
{
    if (!stack) return;
    if (stack->next) stack_destroy(stack->next);

    free(stack);
}

//-----------------------------
typedef struct __tag_map
{
    int x, y;
    int *array;
    int resove;
} MapNode, *Map;

MapNode map_create(int x, int y)
{
    MapNode map = {.x= x, .y = y};
    map.array = malloc(x * y * sizeof(int));

    srand((unsigned int) time(NULL));
    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            map.array[i * y + j] = (rand() % 97 < 67) - 1;
        }
    }
    map.resove = 0;
    map.array[0] = 1;
    map.array[x * y - 1] = 0;  // 设置起点和终点

    return map;
}

bool map_range(Map map, ElemType data)
{
    return data.x >= 0 && data.y >= 0 && data.x < map->x && data.y < map->y;
}

void map_destroy(Map map)
{
    free(map->array);
}

void map_display(Map map, char *str)
{
    printf("\n%d(%s):\n", map->resove, str);
    for (int i = 0; i < map->x; ++i)
    {
        for (int j = 0; j < map->y; ++j)
        {
            printf("%2d%c", map->array[i * map->y + j], "\n "[j < map->y - 1]);
        }
    }
}

void fun(Stack stack, Map map, ElemType *end)
{
    ElemType tmp, now = stack_top(stack).data;

    if (now.x == end->x && now.y == end->y)
    {
        map->resove += 1;
        map_display(map, "END");
        return;
    }

    for (int i = 1; i < 5; ++i)  // 四个方向
    {
        tmp = elem_next(&now, i);
        if (!map_range(map, tmp)) continue;
        if (map->array[tmp.x * map->y + tmp.y]) continue;

        map->array[tmp.x * map->y + tmp.y] = map->array[now.x * map->y + now.y] + 1;
        stack_push(stack, tmp);

        fun(stack, map, end);

        stack_pop(stack, &tmp);
        map->array[tmp.x * map->y + tmp.y] = 0;
    }
}

int main(int argc, char *argv[])
{
    Stack stack = stack_create();
    MapNode map = map_create(7, 9);

    ElemType beg = {0}, end = {.x = 6, .y = 8};

    map_display(&map, "INIT");

    stack_push(stack, beg);

    fun(stack, &map, &end);
    if (!map.resove) printf("No Resove\n");

    map_destroy(&map);
    stack_destroy(stack);

    return EXIT_SUCCESS;
}