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

Classes
struct	coord_s
	Structure de données pour une coordonnée. More...

struct	grid_s
	Structure de données pour une grille. More...

struct	element_s
	Structure de données pour un élément de pile ou de file contenant une coordonnée. More...

struct	stack_s
	Structure de données pour une pile (LIFO) More...

struct	queue_s
	Structure de données pour une file (FIFO) More...

Typedefs
typedef struct element_s	element_s
	Structure de données pour un élément de pile ou de file contenant une coordonnée.

Enumerations
enum	{ WALL = '#' , EMPTY = '.' , START = 'T' , COMMAND = 'C' , UNKNOWN = '?' , UNEXPLORED = 'U' , EXPLORED = 'E' , SKIPPED = 'S' , PLANNED = 'N' }
	Constantes pour les caractères de la grille. More...

Functions
stack_s *	create_stack ()
	Crée une pile vide (LIFO)

void	push_coordinate (stack_s *stack, int x, int y)
	Empile une coordonnée sur la pile.

coord_s	pop (stack_s *stack)
	Dépile une coordonnée de la pile et la retourne.

size_t	size (stack_s *stack)
	Retourne la taille de la pile (nombre d'éléments)

void	free_stack (stack_s *stack)
	Libère la pile (et ses éléments)

queue_s *	create_queue ()
	Crée une file vide (FIFO)

void	enqueue_coordinate (queue_s *queue, int x, int y)
	Enfile des coordonnées à la file (à la fin)

coord_s	dequeue (queue_s *queue)
	Defile des coordonnées de la file et les retourne.

bool	is_empty_q (queue_s *queue)
	Vérifie si la file est vide.

bool	is_in_queue (queue_s *queue, int x, int y)
	Vérifie si des coordonnées sont dans la file.

void	free_queue (queue_s *queue)
	Libère la file (et ses éléments)

bool	is_valid (grid_s *grid, int x, int y)
	Vérifie si une coordonnée est valide (dans la grille)

bool	is_next_to (int x, int y, int x2, int y2)
	Vérifie si deux coordonnées sont voisines (adjacentes) (pas en diagonale) et non égales.

void	read_input (grid_s grid, int x, int *y)
	Lit l'entrée standard et modifie les coordonnées du joueur.

grid_s *	create_grid (int nb_rows, int nb_cols, char letter)
	Initialise une grille avec une lettre donnée.

coord_s	found_char (grid_s *grid, char c)
	Recherche la position d'un caractère dans une grille.

bool	is_useless (grid_s *grid, int x, int y)
	Indique si une case est inutile à explorer.

void	free_grid (grid_s *grid)
	Libère une grille de lettres.

void	free_int_grid (int **grid, int nb_rows)
	Libère une grille d'entiers.

stack_s *	dijkstra (grid_s *grid, int start_x, int start_y, int end_x, int end_y)
	Implémente l'algorithme de Dijkstra.

void	direction (int actual_x, int actual_y, int x, int y)
	Renvoie dans quelle direction aller pour se rendre à une case.

void	go_to (grid_s grid, int x, int *y, int end_x, int end_y)
	Va à une case de destination depuis la position actuelle du joueur en utilisant l'algorithme de Dijkstra.

int	main ()
	Fonction principale.

Typedef Documentation

◆ element_s

typedef struct element_s element_s

Structure de données pour un élément de pile ou de file contenant une coordonnée.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Constantes pour les caractères de la grille.

Enumerator
WALL	Mur.
EMPTY	Case vide.
START	Case de départ et d'arrivée.
COMMAND	Case de commande.
UNKNOWN	Case inconnue (non découverte)
UNEXPLORED	Case non explorée.
EXPLORED	Case explorée.
SKIPPED	Case ignorée (aucun intérêt d'explorer cette case)
PLANNED	Case planifiée (à explorer)

Function Documentation

◆ create_grid()

grid_s * create_grid	(	int	nb_rows,
		int	nb_cols,
		char	letter
	)

Initialise une grille avec une lettre donnée.

Parameters

nb_rows	Le nombre de lignes
nb_cols	Le nombre de colonnes
letter	La lettre à mettre dans la grille

Returns: La grille nouvellement créée

◆ create_queue()

queue_s * create_queue ( )

Crée une file vide (FIFO)

Returns: La file nouvellement créée

◆ create_stack()

stack_s * create_stack ( )

Crée une pile vide (LIFO)

Returns: La pile nouvellement créée

◆ dequeue()

coord_s dequeue ( queue_s * queue )

Defile des coordonnées de la file et les retourne.

Parameters

queue La file sur laquelle defiler les coordonnées

Returns: Les coordonnées défilées

◆ dijkstra()

stack_s * dijkstra	(	grid_s *	grid,
		int	start_x,
		int	start_y,
		int	end_x,
		int	end_y
	)

Implémente l'algorithme de Dijkstra.

L'algorithme de Dijkstra permet de trouver le plus court chemin entre deux points d'une grille.

See also: https://fr.wikipedia.org/wiki/Plus_court_chemin; 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.

Parameters

grid	La grille dans laquelle chercher le chemin
start_x	La coordonnée x de départ
start_y	La coordonnée y de départ
end_x	La coordonnée x de destination
end_y	La coordonnée y de destination

Returns: La pile contenant le chemin le plus court ou NULL si le chemin n'existe pas

◆ direction()

void direction	(	int	actual_x,
		int	actual_y,
		int	x,
		int	y
	)

Renvoie dans quelle direction aller pour se rendre à une case.

Parameters

actual_x	La coordonnée x de départ
actual_y	La coordonnée y de départ
x	La coordonnée x de destination
y	La coordonnée y de destination

◆ enqueue_coordinate()

void enqueue_coordinate	(	queue_s *	queue,
		int	x,
		int	y
	)

Enfile des coordonnées à la file (à la fin)

Parameters

queue	La file sur laquelle ajouter les coordonnées
x	La coordonnée x
y	La coordonnée y

◆ found_char()

coord_s found_char	(	grid_s *	grid,
		char	c
	)

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).

Parameters

grid	La grille à parcourir
c	Le caractère à rechercher

Returns: La position du caractère dans la grille

◆ free_grid()

void free_grid ( grid_s * grid )

Libère une grille de lettres.

Parameters

grid	La grille à libérer

◆ free_int_grid()

void free_int_grid	(	int **	grid,
		int	nb_rows
	)

Libère une grille d'entiers.

Parameters

grid	La grille à libérer
nb_rows	Le nombre de lignes de la grille

◆ free_queue()

void free_queue ( queue_s * queue )

Libère la file (et ses éléments)

Parameters

queue La file à libérer

◆ free_stack()

void free_stack ( stack_s * stack )

Libère la pile (et ses éléments)

Parameters

stack La pile à libérer

◆ go_to()

void go_to	(	grid_s *	grid,
		int *	x,
		int *	y,
		int	end_x,
		int	end_y
	)

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 also: dijkstra; read_input

Parameters

grid	La grille dans laquelle se déplacer
x	La coordonnée x de la position actuelle du joueur
y	La coordonnée y de la position actuelle du joueur
end_x	La coordonnée x de la case de destination
end_y	La coordonnée y de la case de destination

◆ is_empty_q()

bool is_empty_q ( queue_s * queue )

Vérifie si la file est vide.

Parameters

queue La file à vérifier

Returns: true si la file est vide, false sinon

◆ is_in_queue()

bool is_in_queue	(	queue_s *	queue,
		int	x,
		int	y
	)

Vérifie si des coordonnées sont dans la file.

Parameters

queue	La file à vérifier
x	La coordonnée x
y	La coordonnée y

Returns: true si les coordonnées sont dans la file, false sinon

◆ is_next_to()

bool is_next_to	(	int	x,
		int	y,
		int	x2,
		int	y2
	)

Vérifie si deux coordonnées sont voisines (adjacentes) (pas en diagonale) et non égales.

Parameters

x	La coordonnée x de la première coordonnée
y	La coordonnée y de la première coordonnée
x2	La coordonnée x2 de la deuxième coordonnée
y2	La coordonnée y2 de la deuxième coordonnée

◆ is_useless()

bool is_useless	(	grid_s *	grid,
		int	x,
		int	y
	)

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.

Parameters

grid	La grille dans laquelle se trouve la case
visited	La grille des cases visitées
x	La coordonnée x de la case
y	La coordonnée y de la case

◆ is_valid()

bool is_valid	(	grid_s *	grid,
		int	x,
		int	y
	)

Vérifie si une coordonnée est valide (dans la grille)

Parameters

grid	La grille
x	La coordonnée x
y	La coordonnée y

Returns: true si la coordonnée est valide, false sinon

◆ main()

int main ( )

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.

◆ pop()

coord_s pop ( stack_s * stack )

Dépile une coordonnée de la pile et la retourne.

Parameters

stack La pile sur laquelle dépiler

Returns: La coordonnée dépilée

◆ push_coordinate()

void push_coordinate	(	stack_s *	stack,
		int	x,
		int	y
	)

Empile une coordonnée sur la pile.

Parameters

stack	La pile sur laquelle empiler les coordonnées
x	La coordonnée x
y	La coordonnée y

◆ read_input()

void read_input	(	grid_s *	grid,
		int *	x,
		int *	y
	)

Lit l'entrée standard et modifie les coordonnées du joueur.

Parameters

grid	La grille
x	La coordonnée x du joueur
y	La coordonnée y du joueur

◆ size()

size_t size ( stack_s * stack )

Retourne la taille de la pile (nombre d'éléments)

Parameters

stack La pile dont on veut connaître la taille

Returns: La taille de la pile

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ element_s

Enumeration Type Documentation

◆ anonymous enum

Function Documentation

◆ create_grid()

◆ create_queue()

◆ create_stack()

◆ dequeue()

◆ dijkstra()

◆ direction()

◆ enqueue_coordinate()

◆ found_char()

◆ free_grid()

◆ free_int_grid()

◆ free_queue()

◆ free_stack()

◆ go_to()

◆ is_empty_q()

◆ is_in_queue()

◆ is_next_to()

◆ is_useless()

◆ is_valid()

◆ main()

◆ pop()

◆ push_coordinate()

◆ read_input()

◆ size()