Lumen
Table of Contents
1. Code
2. Présentation du problème
ILS t’ont enfermé dans une pièce carrée…
ILS veulent tout savoir de toi…
ILS t’observent…
ILS ont placé des bougies dans la pièce…
Trouveras-tu des cachettes dans cette pièce ?
Le but est de trouver le nombre de cachettes possibles dans la pièce.
2.1. Inputs
3 informations nous sont données:
- La largeur de la pièce (N).
- Le rayon d’éclairage des bougies (L).
- Enfin, une représentation de la pièce avec les coordonnées des bougies (marquées d’un C).
X X X X X X C X X X X X X X X X X X X X X X X X X
2.2. Output
Il nous est demander de simplement renvoyer le nombre de cachettes possibles. Autrement dit le nombre de case non éclairées.
3. Résolution du problème
3.1. Les inputs
On commence d’abord par récupérer la taille de la pièce et le rayon d’éclairage des bougies.
On initialise ensuite le nombre de cachettes possible au nombre de cases de la pièce.
On récupère ensuite le placement des bougies lignes par lignes. Puis à chaque bougies trouvé on applique la fonction light. La fonction light nous renvoie le nombre de case nouvellement éclairées que l’on déduit du total de cachettes.
On fini simplement par afficher le nombre de cachettes restantes.
int main() { int i; int N; scanf("%d", &N); int L; scanf("%d", &L); bool **room; int hiding_places = N * N; room = malloc(N * sizeof(*room)); for (i = 0; i < N; ++i) { room[i] = malloc(N * sizeof(bool)); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { char cell[4]; scanf("%s", cell); if (cell[0] == 'C') { hiding_places -= light(room, N, L, i, j); } } } for (i = 0; i < N; ++i) { free(room[i]); } free(room); printf("%d\n", hiding_places); return 0; }
3.2. fonction light
La fonction light contient un compteur nommé inlight\boxes contenant le nombre de case nouvellement écalirées.
On parcours alors toutes les cases dans le rayon défini par la puissance d’acalirage de la bougie. On fait appelle à la fonction is\in\room affin de savoir si la case existe. Si cette case est pour l’instant dans l’obscurité, on l’éclaire et on ajoute 1 au compteur.
Enfin, on renvoie le inlight\boxes.
/** * \fn int light(bool **room, int length, int lightning_radius, int x, int y) * \brief Eclaire les cases autour de la bougie (x, y) * \param room La pièce de départ * \param length La longueur de la pièce * \param lightning_radius Rayon d'action de la bougie * \param x Abscisse de la bougie * \param y Ordonée de la bougie * \return Renvoie le nombre de nouvelles cases éclairées */ int light(bool **room, int length, int lightning_radius, int x, int y) { int inlight_boxes = 0; int i, j; for (i = -lightning_radius + 1; i < lightning_radius; ++i) { for (j = -lightning_radius + 1; j < lightning_radius; ++j) { if (is_in_room(length, x + i, y + j) && !room[x + i][y + j]) { room[x + i][y + j] = 1; ++inlight_boxes; } } } return inlight_boxes; }
3.3. fonction is\in\room
Cett fonction teste si les coordonées données en arguments appartiennent à la pièce.
/** * \fn bool is_in_room(int length, int x, int y) * \brief Teste si la case existe * \param length La longueur de la pièce * \param x Abscisse de la case à tester * \param y Ordonée de la case à tester * \return Renvoie 1 si la case existe */ bool is_in_room(int length, int x, int y) { return (x >= 0 && x < length && y >= 0 && y < length); }
4. Tests
Voici 2 tests pour illustrer le propos.
4.1. Test trivial
Le premier étant très simple puisqu’il ne contient qu’une bougie.
4.1.1. INPUT
5 3 X X X X X X C X X X X X X X X X X X X X X X X X X
4.1.2. OUTPUT
9
4.2. Test plus avancé
Voici un test un petit peu plus exigeant puisque la pièce est considérablement plus grande et de même pour le nombre de bougies.
4.2.1. INPUT
20 3 X X X C X C X X X X X X X X X X X X X X X C X X X C X X X X C X X X X C X X X X X X X X X X X X X X X X X C C X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X C X X X X X X X X C X X X X X X X C X X X X X X X X C X X X X X X X X C X X X X C X X X X X X C X X C C C X X X X X X X X X C X X X X X X X X C X X X C X X X X X X X X X C X X C X X X X X X X X X C X X X X X X X X X X X C X C X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X C X X X X X X X X X X C X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X C C X X X X C X X X X X X X X X X X X X X X X C C C X X X X X X X X X X X X X C X X X X X X X C C X X X X X C X X X X X X X X X X X X X C X X X X X X X C X X X X X X X X X C X X X X X C X C X X X X X X X X X X X X X X X X
4.2.2. OUTPUT
34