Lumen

Page web ISIMA
Documentation
Fichier .org source
Défi de programmation - Lumen

1. Introduction

Dans cet exercice, on se situe dans une pièce de taille donnée, des lumières sont présentes dans la pièce. Le but est de déterminer la taille de l’espace non éclairé de la pièce

Exemple (la lumière a un rayon de L = 3 cases) :

La lumière est représentée par un X, la zone jaune est la zone éclairée, on doit déterminer l’aire de la zone grise.

2. Approche utilisée

2.1. Description synoptique

Nous sommes situé dans une salle de N * N cases.
On commence avec aucune lumière, on a donc total (qui représente le nombre de case non élairées) = N*N.
On parcourt chaque case de la salle, quand on trouve une lumière, on compte le nombre de cases pas déjà éclairées qu’elle éclaire désormais. On soustrait ce nombre à total.
On a donc a la fin du programme total qui contient le nombre de cases qui ne sont pas éclairées.

Exemple avec 2 lumières (une limière a un rayon de 2) :

Ici chaque lumière couvre une aire totale de 3*3 = 9 cases, mais on ne comptera que 8 cases pour la lumière verte car une case qu’elle couvre est déjà couverte par la lumière jaune.

2.2. Algorithme

Fonction clear :
Prend en entrée une grille d’entier grid, chaque case contient 0 si elle n’est pas éclairée, une autre valeur sinon. La position x et y de la lumière, N la largeur et hauteur de la grille, L le rayon de la lumière. Cette fonction marque les cases comme éclairée s (parmis celles non marquées) autour la la lumière donnée et renvoie le nombre de cases marquées.
count = 0
Pour chaque case autour de la lumière :

Si la valeur de la case = 0 (elle n’est pas déjà marquée) :
- case = valeur autre que 0
- Incrémentation de count

Renvoyer count

Fonction principale :
N, L : les paramètres donnés par l’exercice
total = N * N
grid = tableau d’entier (tous à 0 au début)
Pour chaque case (x, y) de la pièce :

Si la case est une lumière :
- total = total - clear(grid, x, y, L, N)

Afficher total

3. Résolution

3.1. Programme

/**
 * @file lumen.c
 * @brief Résolution de Lumen
 * @author Rémi SCHIRRA
 * @version 1.0
 * @date 14 avril 2024
 */
#include <stdlib.h>
#include <stdio.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

/**
 * @brief fonction marquant les cases de la grille comme éclairée, autour d'une position donnée
 * et d'une taille de lumière
 * @param x, y La position de la lumière
 * @param L La taille de la lumière
 * @param N La largeur et longueur de la grille
 * @return Le nombre de cases marquées
 */
int clear(int *grid, int x, int y, int L, int N) {
    int count = 0;
    for (int i=max(x-L+1,0); i<min(x+L,N); ++i) {
        for (int j=max(y-L+1,0); j<min(y+L,N); ++j) {
            if (!grid[i*N+j]) {
                grid[i*N+j] = ++count;
            }
        }
    }
    return count;
}

int main() {
    int N, L, total, *grid;

    scanf("%d%d", &N, &L);

    total = N*N;
    grid = malloc(N*N * sizeof(int));

    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            char cell[4];
            scanf("%s", cell);
            if (cell[0] == 'C') {
                total -= clear(grid, i, j, L, N);
            }
        }
    }
    printf("%d\n", total);

    return 0;
}

3.2. Test

A partir du test suivant (lumen.txt) :

5
3
X X X X X
X C X X X
X X X X X
X X X C X
X X X X X

Le programme affiche le nombre de cases dans l’ombre :

4. Comparaison avec une autre solution

A partir de cette solution externe :

// ------------------------------------------------------------------
//                                                              Lumen
// ------------------------------------------------------------------
#include <stdio.h>
// ------------------------------------------------------------------
int map[25][25];
int N,L;
// ------------------------------------------------------------------
void
F(unsigned  int i, unsigned int j, int l){
    if ( i >= N || j >= N || l < map[i][j] ) return;
    map[i][j] = l--;
    F( i-1 , j-1 , l) ; F( i-1 , j   , l) ; F( i-1 , j+1 , l) ;
    F( i   , j-1 , l) ;                   ; F( i   , j+1 , l) ;
    F( i+1 , j-1 , l) ; F( i+1 , j   , l) ; F( i+1 , j+1 , l) ;
}
// ------------------------------------------------------------------
main() {
    scanf("%d %d\n", &N, &L);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            char buf[2];
            scanf("%s",buf);
            F( i , j , *buf=='X' ? 0 : L);
        }
    }
    int result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            result += map[i][j] == 0;
        }
    }
    printf("%d",result);
}

Cette solution propose une fonction récursive afin d’actualiser les cases autour de chaque lumière. Elle compte ensuite le nombre de cases ayant une valeur de 0.

5. Bilan

L’exercice a été simple à résoudre, je n’ai pas rencontré de difficultés.