Rapport sur Lumen

Ma stratégie est la suivante, remplir un tableau similaire à celui de l’exemple ci dessus, puis compter le nombre de cases non éclairées et l’afficher. Comme on nous demande uniquement le nombre de cases sombres, il n’est pas nécessaire de s’occuper de la valeur exacte de l’éclairement de chaque case du tableau, il suffit de leur assigner une valeur différente de 0. Ainsi, seules les cases non éclairées auront pour valeur 0. J’ai donc diviser mon programme en plusieurs parties afin de mettre en place ma stratégie de résolution.

Dans ce programme, on se base essentiellement sur un mécanisme que je vais décrire ci-dessous. Le fait d’incrémenter chaque case éclairé, afin de créer une zone carrée, dont le centre est la bougie.

Pour ce faire, on va d’abord détecter les bougies. Dès qu’une bougie est détectée, on va regarde si les cases que l’on souhaite modifier existent, si elles existent on va alors les incrémenter de 1. Mais rentrons plus en détail sur la façon dont on regarde les cases. On va tout d’abord s’occuper des cases qui sont à gauches de la bougies. Alors on va incrémenter la case qui se situe à gauche et sur la même ligne que la bougie. A partir de cette case, on va incrémenter toutes les cases qui se situent en dessous et au dessus d’elle. Puis on va utiliser le même processus à droite. Ensuite, on va répéter l’opération pour des cases de plus en plus éloignées de la bougie, jusqu’à ce que la bougie ne soit plus assez puissante pour éclairer la case d’après.

Enfin, on va éclairer les cases situées sur la colonne de la bougie, en haut et en bas.

Afin de mieux comprendre ce mécanisme, voici un schéma plus détaillé du fonctionnement de cette boucle. La bougie représentée a une puissance de 3.

Dans ce schéma, les cases rouges représentent les bougies, et les cases bleues sont les cases que l’on cherche à remplir. Les couleurs les plus foncées sont celles que l’on rempli en premier. Lors de la première étape, on rempli le début de la partie gauche, puis on va remplir le début de la partie droite. A l’étape 3, on voit que le processus lors duquel l’on rempli à gauche et à droite est terminé. Enfin, lors de l’étape 4 on a rempli la colonne de la bougie. Le remplissage de la zone est donc terminée, et toutes les cases blanches sont des cases d’ombres, où on peut se cacher.

Voici ci dessous le code complet m’ayant permis de résoudre le problème.

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

int main(){

// Initialisation des variables
    int N;
    scanf("%d", &N); // Dimension du tableau
    int L;
    scanf("%d", &L); // Luminosité
    char tab[255][255]; // Grille
    int i;
    int j;
    int h;
    int l;
    int count=0;

// Création du tableau
 for (i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            char cell[4];
            scanf("%s", cell); // Récupération du caractère de chaque case
            if(cell[0]=='C'){
                tab[i][j]='C'; // Place les bougies
            }else{
                tab[i][j]='0';  // Remplace les X par des 0
            }
        }
    }

// Boucle principale
for (i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if((tab[i][j]>='A')&&(tab[i][j]<='Z')){ // Si on détecte une bougie
                for(l = 1;l<L; l++){

                    if((j-l>=0)&&(tab[i][j-l]<L+48)){ // Place la lumière à gauche de la bougie
                        tab[i][j-l]+=1;

                        if(i!=0){
                            for(h=1;h<L;h++){
                                tab[i-h][j-l]+=1;
                            }
                        }
                        if(i!=N-1){
                            for(h=0;h<L;h++){
                                tab[i+h][j-l]+=1;
                            }
                        }
                    }

                    if((j+l<N)&&(tab[i][j+l]<L+48)){ // Place la lumière à droite de la bougie
                        tab[i][j+l]+=1;

                        if(i!=0){
                            for(h=1;h<L;h++){
                                tab[i-h][j+l]+=1;
                            }
                        }
                        if(i!=N-1){
                            for(h=0;h<L;h++){
                                tab[i+h][j+l]+=1;
                            }
                        }
                    }

                    if((i-l>=0)&&(tab[i-l][j]<L+48)){ // Place la lumière sur la colonne de la bougie (au dessus)
                        tab[i-l][j]+=1;
                    }

                    if((i+l<N)&&(tab[i+l][j]<L+48)){ // Place la lumière sur la colonne de la bougie (en dessous)
                        tab[i+l][j]+=1;
                    }
                }
            }
        }
    }

// Comptage des 0
for (i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(tab[i][j]=='0'){
                count++;
            }
        }
}

// Affichage du résultat
printf("%d\n",count);
    return 0;
    }

Afin de coder ce programme et de le valider, il a fallut passer plusieurs tests. Alors voici ci dessous les tests qui m’ont permi de résoudre ce problème.

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) ;
}

Dans cette première partie, l’utilisateur définit sa fonction récursive qui sera le coeur de son programme. Il va d’abord tester si les valeurs de i et j qui lui sont données (les coordonnées de la case traitée) ne sont pas sur un bord de la pièce, auquel cas, il ne pourra pas executer le programme pour ces valeurs là. Ensuite, il va enlever 1 à la valeur de la lumière, ce qui fait que sa récursion va s’arréter quand la lumière ne sera pas assez puissante pour atteindre la case suivante.

Enfin, il va appeler sa fonction avec les coordonnées de chaque case qui entoure la bougie. Puis, grace au mécanisme de récursion, il va rappeler sa fonction avec la valeur de chaque case qui entoure les cases qui entourent la bougie, et ainsi de suite. De façon plus claire, il va remplir la zone autour de la bougie à l’aide de carré. Afin de mieux comprendre ce mécanisme, voici un schéma explicatif de son fonctionnement.

Dans ce schéma, les cases rouges représentent la bougie, et le cases bleues, les zones éclairées par la bougie. Si une case est en bleue foncé, cela signifit que le programme l’a incrémenté au moins deux fois. Ici, la puissance de la bougie est de 3. Lors de la première étape, on va remplir les cases se situant tout autour de la bougie. Puis dans la seconde étape, on va appliquer la récursion pour la case se trouvant à la position (i-1,j-1), où (i,j) sont les coordonnées de la bougie. Ensuite, dans l’étape 3 on va en plus appliquer la récursion aux cases de coordonnées (i-1,j) et (i-1,j+1). Enfin, dans l’étape 4 on va appliquer la récusrion à toutes les autres cases, ce qui va nous permettre d’avoir la zone complète éclairée par la bougie.

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);
        }
    }

Dans cette deuxième partie, l’utilisateur va pour chaque caractère du tableau tester si c’est une bougie. Si s’en est une, alors on va appliquer la fonction récursive aux coordonnées de la bougie afin de compléter le tableau en conséquence

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

Dans cette troisième partie, on va simplement compter le nombre de 0 restant dans le tableau, et on va afficher la valeur du compteur, qui correspond à notre résultat final.

Voici ci dessous le code commenté de l’utilisateur Alain Delpuch en entier.

#include <stdio.h>


// Instanciation des variables

int map[25][25];
int N,L;

void
// Definition de la fonction
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(){
// Calcul de la solution
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);
        }
    }

// Affichage du résultat
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);
    }