Rapport : Labyrinthe

/**
 * @brief Constantes pour les caractères de la grille
 */
enum {
    // map
    WALL = '#', ///< Mur
    EMPTY = '.', ///< Case vide
    START = 'T', ///< Case de départ et d'arrivée
    COMMAND = 'C', ///< Case de commande
    UNKNOWN = '?', ///< Case inconnue (non découverte)

    // custom
    UNEXPLORED = 'U', ///< Case non explorée
    EXPLORED = 'E', ///< Case explorée
    SKIPPED = 'S', ///< Case ignorée (aucun intérêt d'explorer cette case)
    PLANNED = 'N', ///< Case planifiée (à explorer)
};

/**
 * @brief Structure de données pour une coordonnée
 */
typedef struct {
    int x; ///< La coordonnée x
    int y; ///< La coordonnée y
} coord_s;

/**
 * @brief Structure de données pour une grille
 */
typedef struct {
    char **grid; ///< La grille (tableau à deux dimensions de caractères)
    int nb_lines; ///< Le nombre de lignes de la grille
    int nb_columns; ///< Le nombre de colonnes de la grille
} grid_s;

/**
 * @brief Structure de données pour un élément de pile ou de file contenant une coordonnée
 */
typedef struct element_s {
    coord_s position; ///< La coordonnée
    struct element_s *previous; ///< L'élément précédent (NULL si premier élément)
} element_s;

/**
 * @brief Structure de données pour une pile (LIFO)
 */
typedef struct {
    element_s *last; ///< Le dernier élément de la pile (NULL si vide)
} stack_s;

/**
 * @brief Structure de données pour une file (FIFO)
 */
typedef struct {
    element_s *first; ///< Le premier élément de la file (NULL si vide)
    element_s *last; ///< Le dernier élément de la file (NULL si vide)
} queue_s;

/**
 * @brief Crée une pile vide (LIFO)
 * @return La pile nouvellement créée
 */
stack_s *create_stack() {
    stack_s *stack = malloc(sizeof *stack);
    stack->last = NULL;
    return stack;
}

/**
 * @brief Empile une coordonnée sur la pile
 * @param stack La pile sur laquelle empiler les coordonnées
 * @param x La coordonnée x
 * @param y La coordonnée y
 */
void push_coordinate(stack_s *stack, int x, int y) {
    element_s *element = malloc(sizeof *element);
    element->position.x = x;
    element->position.y = y;
    element->previous = stack->last;
    stack->last = element;
}

/**
 * @brief Dépile une coordonnée de la pile et la retourne
 * @param stack La pile sur laquelle dépiler
 * @return La coordonnée dépilée
 */
coord_s pop(stack_s *stack) {
    element_s *element = stack->last;
    stack->last = element->previous;
    coord_s position = element->position;
    free(element);
    return position;
}

/**
 * @brief Retourne la taille de la pile (nombre d'éléments)
 * @param stack La pile dont on veut connaître la taille
 * @return La taille de la pile
 */
size_t size(stack_s *stack) {
    int n = 0;
    element_s *current = stack->last;
    while (current != NULL) {
        n++;
        current = current->previous;
    }
    return n;
}

/**
 * @brief Libère la pile (et ses éléments)
 * @param stack La pile à libérer
 */
void free_stack(stack_s *stack) {
    element_s *current = stack->last;
    while (current != NULL) {
        element_s *next = current->previous;
        free(current);
        current = next;
    }
    free(stack);
}

/**
 * @brief Crée une file vide (FIFO)
 * @return La file nouvellement créée
 */
queue_s *create_queue() {
    queue_s *queue = malloc(sizeof *queue);
    queue->first = NULL;
    queue->last = NULL;
    return queue;
}

/**
 * @brief Enfile des coordonnées à la file (à la fin)
 * @param queue La file sur laquelle ajouter les coordonnées
 * @param x La coordonnée x
 * @param y La coordonnée y
 */
void enqueue_coordinate(queue_s *queue, int x, int y) {
    element_s *element = malloc(sizeof *element);
    element->position.x = x;
    element->position.y = y;
    element->previous = NULL;
    if (queue->first == NULL) {
        queue->first = element;
    } else {
        queue->last->previous = element;
    }
    queue->last = element;
}

/**
 * @brief Defile des coordonnées de la file et les retourne
 * @param queue La file sur laquelle defiler les coordonnées
 * @return Les coordonnées défilées
 */
coord_s dequeue(queue_s *queue) {
    element_s *element = queue->first;
    queue->first = element->previous;
    coord_s position = element->position;
    free(element);
    return position;
}

/**
 * @brief Vérifie si la file est vide
 * @param queue La file à vérifier
 * @return true si la file est vide, false sinon
 */
bool is_empty_q(queue_s *queue) {
    return queue->first == NULL;
}

/**
 * @brief Vérifie si des coordonnées sont dans la file
 * @param queue La file à vérifier
 * @param x La coordonnée x
 * @param y La coordonnée y
 * @return true si les coordonnées sont dans la file, false sinon
 */
bool is_in_queue(queue_s *queue, int x, int y) {
    element_s *current = queue->first;
    while (current != NULL) {
        if (current->position.x == x && current->position.y == y) {
            return true;
        }
        current = current->previous;
    }
    return false;
}

/**
 * @brief Libère la file (et ses éléments)
 * @param queue La file à libérer
 */
void free_queue(queue_s *queue) {
    element_s *current = queue->first;
    while (current != NULL) {
        element_s *next = current->previous;
        free(current);
        current = next;
    }
    free(queue);
}

/**
 * @brief Vérifie si une coordonnée est valide (dans la grille)
 * @param grid La grille
 * @param x La coordonnée x
 * @param y La coordonnée y
 * @return true si la coordonnée est valide, false sinon
 */
bool is_valid(grid_s *grid, int x, int y) {
    return x >= 0 && x < grid->nb_columns && y >= 0 && y < grid->nb_lines;
}

/**
 * @brief Vérifie si deux coordonnées sont voisines (adjacentes) (pas en diagonale) et non égales
 * @param x La coordonnée x de la première coordonnée
 * @param y La coordonnée y de la première coordonnée
 * @param x2 La coordonnée x2 de la deuxième coordonnée
 * @param y2 La coordonnée y2 de la deuxième coordonnée
 */
bool is_next_to(int x, int y, int x2, int y2) {
    return (x == x2 && (y == y2 - 1 || y == y2 + 1)) || (y == y2 && (x == x2 - 1 || x == x2 + 1));
}

/**
 * @brief Lit l'entrée standard et modifie les coordonnées du joueur
 * @param grid La grille
 * @param x La coordonnée x du joueur
 * @param y La coordonnée y du joueur
 */
void read_input(grid_s *grid, int *x, int *y) {
    scanf("%d%d", y, x);
    for (int i = 0; i < grid->nb_lines; i++) {
        scanf("%s", grid->grid[i]);
    }
}

/**
 * @brief Initialise une grille avec une lettre donnée
 * @param nb_rows Le nombre de lignes
 * @param nb_cols Le nombre de colonnes
 * @param letter La lettre à mettre dans la grille
 * @return La grille nouvellement créée
 */
grid_s *create_grid(int nb_rows, int nb_cols, char letter) {
    grid_s *grid = malloc(sizeof *grid);
    grid->nb_lines = nb_rows;
    grid->nb_columns = nb_cols;
    grid->grid = malloc(nb_rows * sizeof *grid->grid);
    for (int i = 0; i < nb_rows; i++) {
        grid->grid[i] = malloc(nb_cols * sizeof *grid->grid[i]);
        for (int j = 0; j < nb_cols; j++) {
            grid->grid[i][j] = letter;
        }
    }
    return grid;
}

/**
 * @brief Recherche la position d'un caractère dans une grille
 *
 * La fonction parcourt la grille et renvoie la position du caractère.
 * Si le caractère n'est pas trouvé, la fonction renvoie la position (-1, -1).
 *
 * @param grid La grille à parcourir
 * @param c Le caractère à rechercher
 * @return La position du caractère dans la grille
 */
coord_s found_char(grid_s *grid, char c) {
    for (int i = 0; i < grid->nb_lines; i++) {
        for (int j = 0; j < grid->nb_columns; j++) {
            if (grid->grid[i][j] == c) {
                coord_s coord = {j, i};
                return coord;
            }
        }
    }
    return (coord_s) {-1, -1};
}

/**
 * @brief Indique si une case est inutile à explorer
 *
 * Une case est inutile à explorer si elle est entourée de murs ou de cases déjà visitées/connues.
 *
 * @param grid La grille dans laquelle se trouve la case
 * @param visited La grille des cases visitées
 * @param x La coordonnée x de la case
 * @param y La coordonnée y de la case
 */
bool is_useless(grid_s *grid, int x, int y) {

    // cul-de-sac
    int nb_walls = 0;
    for (int i = x - 1; i < x + 2; i++) {
        for (int j = y - 1; j < y + 2; j++) {
            if (is_valid(grid, i, j) && is_next_to(i, j, x, y) && grid->grid[j][i] == WALL) {
                nb_walls++;
            }
        }
    }
    if (nb_walls == 3) {
        return true;
    }

    // entouré de cases connues
    for (int i = x - 3; i < x + 4; i++) {
        for (int j = y - 3; j < y + 4; j++) {
            if (is_valid(grid, i, j) && !(i == x && j == y) && grid->grid[j][i] == UNKNOWN) {
                return false;
            }
        }
    }
    return true;
}

/**
 * @brief Libère une grille de lettres
 * @param grid La grille à libérer
 */
void free_grid(grid_s *grid) {
    for (int i = 0; i < grid->nb_lines; i++) {
        free(grid->grid[i]);
    }
    free(grid->grid);
    free(grid);
}

/**
 * @brief Libère une grille d'entiers
 * @param grid La grille à libérer
 * @param nb_rows Le nombre de lignes de la grille
 */
void free_int_grid(int **grid, int nb_rows) {
    for (int i = 0; i < nb_rows; i++) {
        free(grid[i]);
    }
    free(grid);
}

/**
 * @brief Implémente l'algorithme de Dijkstra
 *
 * L'algorithme de Dijkstra permet de trouver le plus court chemin entre deux points d'une grille.
 * @see https://fr.wikipedia.org/wiki/Plus_court_chemin
 * @see https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
 *
 * La variable `distances` est un tableau d'entiers qui contient la distance entre le point de départ et chaque case de la grille (ou -1 si la case n'est pas accessible).
 * La file contient les coordonnées des prochaines cases à calculer.
 * La pile contient les coordonnées du chemin le plus court.
 *
 * Si le chemin n'existe pas, la fonction renvoie NULL.
 * Si le chemin existe, la fonction renvoie une pile contenant les coordonnées du chemin.
 * @note Pour se déplacer, il faut dépiler la pile.
 * @warning La pile doit être libérée avec la fonction free_stack.
 *
 * @param grid La grille dans laquelle chercher le chemin
 * @param start_x La coordonnée x de départ
 * @param start_y La coordonnée y de départ
 * @param end_x La coordonnée x de destination
 * @param end_y La coordonnée y de destination
 * @return La pile contenant le chemin le plus court ou NULL si le chemin n'existe pas
 */
stack_s *dijkstra(grid_s *grid, int start_x, int start_y, int end_x, int end_y) {
    // On initialise un tableau de distances à -1
    int **distances = malloc(grid->nb_lines * sizeof *distances);
    for (int i = 0; i < grid->nb_lines; i++) {
        distances[i] = malloc(grid->nb_columns * sizeof *distances[i]);
        for (int j = 0; j < grid->nb_columns; j++) {
            distances[i][j] = -1;
        }
    }

    // On initialise la distance de la case de départ à 0
    distances[start_y][start_x] = 0;

    queue_s *queue = create_queue();
    enqueue_coordinate(queue, start_x, start_y);
    bool found = false;

    // On parcourt la file jusqu'à trouver la destination ou jusqu'à ce qu'elle soit vide
    while (!found && !is_empty_q(queue)) {
        coord_s position = dequeue(queue);
        int x = position.x;
        int y = position.y;
        int distance = distances[y][x];

        int i, j;
        for (i = x - 1; i < x + 2; i++) {
            for (j = y - 1; j < y + 2; j++) {
                if (is_valid(grid, i, j) && is_next_to(i, j, x, y)) {
                    if (grid->grid[j][i] != WALL && grid->grid[j][i] != UNKNOWN && distances[j][i] == -1) {
                        if (!is_in_queue(queue, i, j)) {
                            enqueue_coordinate(queue, i, j);
                            distances[j][i] = distance + 1;

                            if (i == end_x && j == end_y) {
                                found = true;
                                break;
                            }
                        }
                    }
                }
            }
            if (found) {
                break;
            }
        }
    }
    free_queue(queue);

    // si la case de destination est toujours à -1, on n'a pas trouvé de chemin, on renvoie NULL
    if (distances[end_y][end_x] == -1) {
        free_int_grid(distances, grid->nb_lines);
        return NULL;
    }

    // sinon, on reconstruit le chemin depuis la destination jusqu'à l'origine
    stack_s *path = create_stack();

    int x = end_x;
    int y = end_y;
    int i = distances[end_y][end_x];

    for (; i > 0; i--) {
        push_coordinate(path, x, y);
        
        int j, k;
        found = false;
        for (j = x - 1; j < x + 2; j++) {
            for (k = y - 1; k < y + 2; k++) {
                if (is_valid(grid, j, k) && is_next_to(j, k, x, y) && distances[k][j] == i - 1) {
                    x = j;
                    y = k;
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }
    }
    free_int_grid(distances, grid->nb_lines);
    return path;
}

/**
 * @brief Renvoie dans quelle direction aller pour se rendre à une case
 * @param actual_x La coordonnée x de départ
 * @param actual_y La coordonnée y de départ
 * @param x La coordonnée x de destination
 * @param y La coordonnée y de destination
 */
void direction(int actual_x, int actual_y, int x, int y) {
    if (actual_x < x) {
        printf("RIGHT\n");
    } else if (actual_x > x) {
        printf("LEFT\n");
    } else if (actual_y < y) {
        printf("DOWN\n");
    } else if (actual_y > y) {
        printf("UP\n");
    }
}

/**
 * @brief Va à une case de destination depuis la position actuelle du joueur en utilisant l'algorithme de Dijkstra
 *
 * La fonction trouve le plus court chemin entre la position actuelle et la case de destination.
 * Elle déplace le joueur en suivant ce chemin et en lisant les entrées.
 * La dernière case du chemin est la case d'arrivée passée en paramètre et elle n'est pas lue.
 *
 * @note La fonction ne vérifie pas si la case de destination est accessible.
 *
 * @see dijkstra
 * @see read_input
 *
 * @param grid La grille dans laquelle se déplacer
 * @param x La coordonnée x de la position actuelle du joueur
 * @param y La coordonnée y de la position actuelle du joueur
 * @param end_x La coordonnée x de la case de destination
 * @param end_y La coordonnée y de la case de destination
 */
void go_to(grid_s *grid, int *x, int *y, int end_x, int end_y) {
    stack_s *path = dijkstra(grid, *x, *y, end_x, end_y);

    int i = size(path);
    for (; i > 1; i--) {
        coord_s coord = pop(path);
        direction(*x, *y, coord.x, coord.y);
        read_input(grid, x, y);
    }

    coord_s coord = pop(path);
    direction(*x, *y, coord.x, coord.y);

    free_stack(path);
}

/**
 * @brief Fonction principale
 *
 * La fonction commence par lire les entrées et les stocker.
 * Ensuite, elle explore la grille à la recherche de la salle de commande à l'aide d'une pile.
 * Lorsque la salle de commande est trouvée et qu'il existe un chemin de la salle de commande à la position de départ en moins de `rounds` tours, on arrête l'exploration.
 * On se déplace ensuite vers la salle de commande.
 * Enfin, on retourne à la position de départ.
 */
int main() {
    // Lecture des entrées
    int nb_rows, nb_cols, rounds, x, y;
    scanf("%d%d%d", &nb_rows, &nb_cols, &rounds);

    // Initialisation des structures
    grid_s *grid = create_grid(nb_rows, nb_cols, UNKNOWN);
    grid_s *visited = create_grid(nb_rows, nb_cols, UNEXPLORED);
    stack_s *stack = create_stack();

    // Exploration de la grille
    while (1) {
        read_input(grid, &x, &y);
        visited->grid[y][x] = EXPLORED;

        coord_s command = found_char(grid, COMMAND);
        if (command.x != -1) {
            coord_s start = found_char(grid, START);
            stack_s *path = dijkstra(grid, command.x, command.y, start.x, start.y);
            if (path != NULL) {
                if ((int) size(path) <= rounds) {
                    free_stack(path);
                    break;
                }
                free_stack(path);
            }
        }

        for (int i = x - 1; i < x + 2; i++) {
            for (int j = y - 1; j < y + 2; j++) {
                if (is_valid(grid, i, j) && is_next_to(i, j, x, y)) {
                    if (grid->grid[j][i] == EMPTY && visited->grid[j][i] == UNEXPLORED) {
                        push_coordinate(stack, i, j);
                        visited->grid[j][i] = PLANNED;
                    }
                }
            }
        }

        coord_s next = pop(stack);
        while (is_useless(grid, next.x, next.y) || grid->grid[next.y][next.x] == COMMAND) {
            visited->grid[next.y][next.x] = SKIPPED;
            next = pop(stack);
        }

        go_to(grid, &x, &y, next.x, next.y);
    }

    // Déplacement vers la salle de commande
    coord_s command = found_char(grid, COMMAND);
    go_to(grid, &x, &y, command.x, command.y);
    read_input(grid, &x, &y);

    // Retour à la position de départ
    coord_s start = found_char(grid, START);
    go_to(grid, &x, &y, start.x, start.y);

    // Libération de la mémoire
    free_grid(grid);
    free_grid(visited);
    free_stack(stack);

    return 0;
}

/**
 * @file main.c
 * @author GIRARD Jules
 * @date 28/04/2023
 * @version 1.0
 * @brief Codingame : Le labyrinthe
 *
 * Le but de ce projet est de résoudre le problème du labyrinthe de Codingame.
 * Le programme doit lire une grille de labyrinthe et trouver le chemin le plus court pour atteindre la case de commande et revenir à la case de départ.
 * @see https://www.codingame.com/training/hard/the-labyrinth
 */

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

/**
 * @brief Constantes pour les caractères de la grille
 */
enum {
    // map
    WALL = '#', ///< Mur
    EMPTY = '.', ///< Case vide
    START = 'T', ///< Case de départ et d'arrivée
    COMMAND = 'C', ///< Case de commande
    UNKNOWN = '?', ///< Case inconnue (non découverte)

    // custom
    UNEXPLORED = 'U', ///< Case non explorée
    EXPLORED = 'E', ///< Case explorée
    SKIPPED = 'S', ///< Case ignorée (aucun intérêt d'explorer cette case)
    PLANNED = 'N', ///< Case planifiée (à explorer)
};

/**
 * @brief Structure de données pour une coordonnée
 */
typedef struct {
    int x; ///< La coordonnée x
    int y; ///< La coordonnée y
} coord_s;

/**
 * @brief Structure de données pour une grille
 */
typedef struct {
    char **grid; ///< La grille (tableau à deux dimensions de caractères)
    int nb_lines; ///< Le nombre de lignes de la grille
    int nb_columns; ///< Le nombre de colonnes de la grille
} grid_s;

/**
 * @brief Structure de données pour un élément de pile ou de file contenant une coordonnée
 */
typedef struct element_s {
    coord_s position; ///< La coordonnée
    struct element_s *previous; ///< L'élément précédent (NULL si premier élément)
} element_s;

/**
 * @brief Structure de données pour une pile (LIFO)
 */
typedef struct {
    element_s *last; ///< Le dernier élément de la pile (NULL si vide)
} stack_s;

/**
 * @brief Structure de données pour une file (FIFO)
 */
typedef struct {
    element_s *first; ///< Le premier élément de la file (NULL si vide)
    element_s *last; ///< Le dernier élément de la file (NULL si vide)
} queue_s;

/**
 * @brief Crée une pile vide (LIFO)
 * @return La pile nouvellement créée
 */
stack_s *create_stack() {
    stack_s *stack = malloc(sizeof *stack);
    stack->last = NULL;
    return stack;
}

/**
 * @brief Empile une coordonnée sur la pile
 * @param stack La pile sur laquelle empiler les coordonnées
 * @param x La coordonnée x
 * @param y La coordonnée y
 */
void push_coordinate(stack_s *stack, int x, int y) {
    element_s *element = malloc(sizeof *element);
    element->position.x = x;
    element->position.y = y;
    element->previous = stack->last;
    stack->last = element;
}

/**
 * @brief Dépile une coordonnée de la pile et la retourne
 * @param stack La pile sur laquelle dépiler
 * @return La coordonnée dépilée
 */
coord_s pop(stack_s *stack) {
    element_s *element = stack->last;
    stack->last = element->previous;
    coord_s position = element->position;
    free(element);
    return position;
}

/**
 * @brief Retourne la taille de la pile (nombre d'éléments)
 * @param stack La pile dont on veut connaître la taille
 * @return La taille de la pile
 */
size_t size(stack_s *stack) {
    int n = 0;
    element_s *current = stack->last;
    while (current != NULL) {
        n++;
        current = current->previous;
    }
    return n;
}

/**
 * @brief Libère la pile (et ses éléments)
 * @param stack La pile à libérer
 */
void free_stack(stack_s *stack) {
    element_s *current = stack->last;
    while (current != NULL) {
        element_s *next = current->previous;
        free(current);
        current = next;
    }
    free(stack);
}
/**
 * @brief Crée une file vide (FIFO)
 * @return La file nouvellement créée
 */
queue_s *create_queue() {
    queue_s *queue = malloc(sizeof *queue);
    queue->first = NULL;
    queue->last = NULL;
    return queue;
}

/**
 * @brief Enfile des coordonnées à la file (à la fin)
 * @param queue La file sur laquelle ajouter les coordonnées
 * @param x La coordonnée x
 * @param y La coordonnée y
 */
void enqueue_coordinate(queue_s *queue, int x, int y) {
    element_s *element = malloc(sizeof *element);
    element->position.x = x;
    element->position.y = y;
    element->previous = NULL;
    if (queue->first == NULL) {
        queue->first = element;
    } else {
        queue->last->previous = element;
    }
    queue->last = element;
}

/**
 * @brief Defile des coordonnées de la file et les retourne
 * @param queue La file sur laquelle defiler les coordonnées
 * @return Les coordonnées défilées
 */
coord_s dequeue(queue_s *queue) {
    element_s *element = queue->first;
    queue->first = element->previous;
    coord_s position = element->position;
    free(element);
    return position;
}

/**
 * @brief Vérifie si la file est vide
 * @param queue La file à vérifier
 * @return true si la file est vide, false sinon
 */
bool is_empty_q(queue_s *queue) {
    return queue->first == NULL;
}

/**
 * @brief Vérifie si des coordonnées sont dans la file
 * @param queue La file à vérifier
 * @param x La coordonnée x
 * @param y La coordonnée y
 * @return true si les coordonnées sont dans la file, false sinon
 */
bool is_in_queue(queue_s *queue, int x, int y) {
    element_s *current = queue->first;
    while (current != NULL) {
        if (current->position.x == x && current->position.y == y) {
            return true;
        }
        current = current->previous;
    }
    return false;
}

/**
 * @brief Libère la file (et ses éléments)
 * @param queue La file à libérer
 */
void free_queue(queue_s *queue) {
    element_s *current = queue->first;
    while (current != NULL) {
        element_s *next = current->previous;
        free(current);
        current = next;
    }
    free(queue);
}

/**
 * @brief Vérifie si une coordonnée est valide (dans la grille)
 * @param grid La grille
 * @param x La coordonnée x
 * @param y La coordonnée y
 * @return true si la coordonnée est valide, false sinon
 */
bool is_valid(grid_s *grid, int x, int y) {
    return x >= 0 && x < grid->nb_columns && y >= 0 && y < grid->nb_lines;
}

/**
 * @brief Vérifie si deux coordonnées sont voisines (adjacentes) (pas en diagonale) et non égales
 * @param x La coordonnée x de la première coordonnée
 * @param y La coordonnée y de la première coordonnée
 * @param x2 La coordonnée x2 de la deuxième coordonnée
 * @param y2 La coordonnée y2 de la deuxième coordonnée
 */
bool is_next_to(int x, int y, int x2, int y2) {
    return (x == x2 && (y == y2 - 1 || y == y2 + 1)) || (y == y2 && (x == x2 - 1 || x == x2 + 1));
}

/**
 * @brief Lit l'entrée standard et modifie les coordonnées du joueur
 * @param grid La grille
 * @param x La coordonnée x du joueur
 * @param y La coordonnée y du joueur
 */
void read_input(grid_s *grid, int *x, int *y) {
    scanf("%d%d", y, x);
    for (int i = 0; i < grid->nb_lines; i++) {
        scanf("%s", grid->grid[i]);
    }
}

/**
 * @brief Initialise une grille avec une lettre donnée
 * @param nb_rows Le nombre de lignes
 * @param nb_cols Le nombre de colonnes
 * @param letter La lettre à mettre dans la grille
 * @return La grille nouvellement créée
 */
grid_s *create_grid(int nb_rows, int nb_cols, char letter) {
    grid_s *grid = malloc(sizeof *grid);
    grid->nb_lines = nb_rows;
    grid->nb_columns = nb_cols;
    grid->grid = malloc(nb_rows * sizeof *grid->grid);
    for (int i = 0; i < nb_rows; i++) {
        grid->grid[i] = malloc(nb_cols * sizeof *grid->grid[i]);
        for (int j = 0; j < nb_cols; j++) {
            grid->grid[i][j] = letter;
        }
    }
    return grid;
}

/**
 * @brief Recherche la position d'un caractère dans une grille
 *
 * La fonction parcourt la grille et renvoie la position du caractère.
 * Si le caractère n'est pas trouvé, la fonction renvoie la position (-1, -1).
 *
 * @param grid La grille à parcourir
 * @param c Le caractère à rechercher
 * @return La position du caractère dans la grille
 */
coord_s found_char(grid_s *grid, char c) {
    for (int i = 0; i < grid->nb_lines; i++) {
        for (int j = 0; j < grid->nb_columns; j++) {
            if (grid->grid[i][j] == c) {
                coord_s coord = {j, i};
                return coord;
            }
        }
    }
    return (coord_s) {-1, -1};
}

/**
 * @brief Indique si une case est inutile à explorer
 *
 * Une case est inutile à explorer si elle est entourée de murs ou de cases déjà visitées/connues.
 *
 * @param grid La grille dans laquelle se trouve la case
 * @param visited La grille des cases visitées
 * @param x La coordonnée x de la case
 * @param y La coordonnée y de la case
 */
bool is_useless(grid_s *grid, int x, int y) {

    // cul-de-sac
    int nb_walls = 0;
    for (int i = x - 1; i < x + 2; i++) {
        for (int j = y - 1; j < y + 2; j++) {
            if (is_valid(grid, i, j) && is_next_to(i, j, x, y) && grid->grid[j][i] == WALL) {
                nb_walls++;
            }
        }
    }
    if (nb_walls == 3) {
        return true;
    }

    // entouré de cases connues
    for (int i = x - 3; i < x + 4; i++) {
        for (int j = y - 3; j < y + 4; j++) {
            if (is_valid(grid, i, j) && !(i == x && j == y) && grid->grid[j][i] == UNKNOWN) {
                return false;
            }
        }
    }
    return true;
}

/**
 * @brief Libère une grille de lettres
 * @param grid La grille à libérer
 */
void free_grid(grid_s *grid) {
    for (int i = 0; i < grid->nb_lines; i++) {
        free(grid->grid[i]);
    }
    free(grid->grid);
    free(grid);
}

/**
 * @brief Libère une grille d'entiers
 * @param grid La grille à libérer
 * @param nb_rows Le nombre de lignes de la grille
 */
void free_int_grid(int **grid, int nb_rows) {
    for (int i = 0; i < nb_rows; i++) {
        free(grid[i]);
    }
    free(grid);
}

/**
 * @brief Implémente l'algorithme de Dijkstra
 *
 * L'algorithme de Dijkstra permet de trouver le plus court chemin entre deux points d'une grille.
 * @see https://fr.wikipedia.org/wiki/Plus_court_chemin
 * @see https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
 *
 * La variable `distances` est un tableau d'entiers qui contient la distance entre le point de départ et chaque case de la grille (ou -1 si la case n'est pas accessible).
 * La file contient les coordonnées des prochaines cases à calculer.
 * La pile contient les coordonnées du chemin le plus court.
 *
 * Si le chemin n'existe pas, la fonction renvoie NULL.
 * Si le chemin existe, la fonction renvoie une pile contenant les coordonnées du chemin.
 * @note Pour se déplacer, il faut dépiler la pile.
 * @warning La pile doit être libérée avec la fonction free_stack.
 *
 * @param grid La grille dans laquelle chercher le chemin
 * @param start_x La coordonnée x de départ
 * @param start_y La coordonnée y de départ
 * @param end_x La coordonnée x de destination
 * @param end_y La coordonnée y de destination
 * @return La pile contenant le chemin le plus court ou NULL si le chemin n'existe pas
 */
stack_s *dijkstra(grid_s *grid, int start_x, int start_y, int end_x, int end_y) {
    // On initialise un tableau de distances à -1
    int **distances = malloc(grid->nb_lines * sizeof *distances);
    for (int i = 0; i < grid->nb_lines; i++) {
        distances[i] = malloc(grid->nb_columns * sizeof *distances[i]);
        for (int j = 0; j < grid->nb_columns; j++) {
            distances[i][j] = -1;
        }
    }

    // On initialise la distance de la case de départ à 0
    distances[start_y][start_x] = 0;

    queue_s *queue = create_queue();
    enqueue_coordinate(queue, start_x, start_y);
    bool found = false;

    // On parcourt la file jusqu'à trouver la destination ou jusqu'à ce qu'elle soit vide
    while (!found && !is_empty_q(queue)) {
        coord_s position = dequeue(queue);
        int x = position.x;
        int y = position.y;
        int distance = distances[y][x];

        int i, j;
        for (i = x - 1; i < x + 2; i++) {
            for (j = y - 1; j < y + 2; j++) {
                if (is_valid(grid, i, j) && is_next_to(i, j, x, y)) {
                    if (grid->grid[j][i] != WALL && grid->grid[j][i] != UNKNOWN && distances[j][i] == -1) {
                        if (!is_in_queue(queue, i, j)) {
                            enqueue_coordinate(queue, i, j);
                            distances[j][i] = distance + 1;

                            if (i == end_x && j == end_y) {
                                found = true;
                                break;
                            }
                        }
                    }
                }
            }
            if (found) {
                break;
            }
        }
    }
    free_queue(queue);

    // si la case de destination est toujours à -1, on n'a pas trouvé de chemin, on renvoie NULL
    if (distances[end_y][end_x] == -1) {
        free_int_grid(distances, grid->nb_lines);
        return NULL;
    }

    // sinon, on reconstruit le chemin depuis la destination jusqu'à l'origine
    stack_s *path = create_stack();

    int x = end_x;
    int y = end_y;
    int i = distances[end_y][end_x];

    for (; i > 0; i--) {
        push_coordinate(path, x, y);
        
        int j, k;
        found = false;
        for (j = x - 1; j < x + 2; j++) {
            for (k = y - 1; k < y + 2; k++) {
                if (is_valid(grid, j, k) && is_next_to(j, k, x, y) && distances[k][j] == i - 1) {
                    x = j;
                    y = k;
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }
    }
    free_int_grid(distances, grid->nb_lines);
    return path;
}

/**
 * @brief Renvoie dans quelle direction aller pour se rendre à une case
 * @param actual_x La coordonnée x de départ
 * @param actual_y La coordonnée y de départ
 * @param x La coordonnée x de destination
 * @param y La coordonnée y de destination
 */
void direction(int actual_x, int actual_y, int x, int y) {
    if (actual_x < x) {
        printf("RIGHT\n");
    } else if (actual_x > x) {
        printf("LEFT\n");
    } else if (actual_y < y) {
        printf("DOWN\n");
    } else if (actual_y > y) {
        printf("UP\n");
    }
}

/**
 * @brief Va à une case de destination depuis la position actuelle du joueur en utilisant l'algorithme de Dijkstra
 *
 * La fonction trouve le plus court chemin entre la position actuelle et la case de destination.
 * Elle déplace le joueur en suivant ce chemin et en lisant les entrées.
 * La dernière case du chemin est la case d'arrivée passée en paramètre et elle n'est pas lue.
 *
 * @note La fonction ne vérifie pas si la case de destination est accessible.
 *
 * @see dijkstra
 * @see read_input
 *
 * @param grid La grille dans laquelle se déplacer
 * @param x La coordonnée x de la position actuelle du joueur
 * @param y La coordonnée y de la position actuelle du joueur
 * @param end_x La coordonnée x de la case de destination
 * @param end_y La coordonnée y de la case de destination
 */
void go_to(grid_s *grid, int *x, int *y, int end_x, int end_y) {
    stack_s *path = dijkstra(grid, *x, *y, end_x, end_y);

    int i = size(path);
    for (; i > 1; i--) {
        coord_s coord = pop(path);
        direction(*x, *y, coord.x, coord.y);
        read_input(grid, x, y);
    }

    coord_s coord = pop(path);
    direction(*x, *y, coord.x, coord.y);

    free_stack(path);
}

/**
 * @brief Fonction principale
 *
 * La fonction commence par lire les entrées et les stocker.
 * Ensuite, elle explore la grille à la recherche de la salle de commande à l'aide d'une pile.
 * Lorsque la salle de commande est trouvée et qu'il existe un chemin de la salle de commande à la position de départ en moins de `rounds` tours, on arrête l'exploration.
 * On se déplace ensuite vers la salle de commande.
 * Enfin, on retourne à la position de départ.
 */
int main() {
    // Lecture des entrées
    int nb_rows, nb_cols, rounds, x, y;
    scanf("%d%d%d", &nb_rows, &nb_cols, &rounds);

    // Initialisation des structures
    grid_s *grid = create_grid(nb_rows, nb_cols, UNKNOWN);
    grid_s *visited = create_grid(nb_rows, nb_cols, UNEXPLORED);
    stack_s *stack = create_stack();

    // Exploration de la grille
    while (1) {
        read_input(grid, &x, &y);
        visited->grid[y][x] = EXPLORED;

        coord_s command = found_char(grid, COMMAND);
        if (command.x != -1) {
            coord_s start = found_char(grid, START);
            stack_s *path = dijkstra(grid, command.x, command.y, start.x, start.y);
            if (path != NULL) {
                if ((int) size(path) <= rounds) {
                    free_stack(path);
                    break;
                }
                free_stack(path);
            }
        }

        for (int i = x - 1; i < x + 2; i++) {
            for (int j = y - 1; j < y + 2; j++) {
                if (is_valid(grid, i, j) && is_next_to(i, j, x, y)) {
                    if (grid->grid[j][i] == EMPTY && visited->grid[j][i] == UNEXPLORED) {
                        push_coordinate(stack, i, j);
                        visited->grid[j][i] = PLANNED;
                    }
                }
            }
        }

        coord_s next = pop(stack);
        while (is_useless(grid, next.x, next.y) || grid->grid[next.y][next.x] == COMMAND) {
            visited->grid[next.y][next.x] = SKIPPED;
            next = pop(stack);
        }

        go_to(grid, &x, &y, next.x, next.y);
    }

    // Déplacement vers la salle de commande
    coord_s command = found_char(grid, COMMAND);
    go_to(grid, &x, &y, command.x, command.y);
    read_input(grid, &x, &y);

    // Retour à la position de départ
    coord_s start = found_char(grid, START);
    go_to(grid, &x, &y, start.x, start.y);

    // Libération de la mémoire
    free_grid(grid);
    free_grid(visited);
    free_stack(stack);

    return 0;
}