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

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

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

    new.step = data->step + 1;
    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_queue_node
{
    ElemType data;
    struct __tag_queue_node *next;
} QueueNode, *QueueLink;

typedef struct __tag_queue
{
    QueueLink front;
    QueueLink rear;
} QueueList, *Queue;

Queue queue_create()
{
    Queue queue = malloc(sizeof(QueueList));
    queue->front = queue->rear = malloc(sizeof(QueueNode));
    queue->rear->next = NULL;

    return queue;
}

bool queue_empty(Queue queue)
{
    return queue->front == queue->rear;
}

void queue_en(Queue queue, ElemType elem)
{
    QueueLink t = malloc(sizeof(QueueNode));

    t->data = elem;
    t->next = NULL;

    queue->rear->next = t;
    queue->rear = t;
}

void queue_de(Queue queue, ElemType *elem)
{
    if (queue_empty(queue))
    {
        perror("queue empty");
        exit(EXIT_FAILURE);
    }

    QueueLink t = queue->front->next;

    *elem = t->data;
    queue->front->next = t->next;

    if (t->next == NULL) queue->rear = queue->front;

    free(t);
}

void queue_destroy(Queue queue)
{
    QueueLink p = queue->front, q;
    while (p)
    {
        q = p->next;
        free(p);

        p = q;
    }

    free(queue);
}

//-----------------------------
typedef struct __tag_map
{
    int x, y;
    int *array;
    bool 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.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%s:\n", 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(Queue queue, Map map, ElemType *end)
{
    ElemType tmp, now;
    while (!queue_empty(queue))
    {
        queue_de(queue, &now);

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

        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] = tmp.step;
            queue_en(queue, tmp);
        }
    }
}

int main(int argc, char *argv[])
{
    Queue queue = queue_create();
    MapNode map = map_create(7, 9);

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

    map_display(&map, "INIT");

    queue_en(queue, beg);

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

    map_destroy(&map);
    queue_destroy(queue);

    return EXIT_SUCCESS;
}