Page web ISIMA Fichier .html source

SCHIRRA Rémi Prep ISIMA 1 - 2023-2024

Défi de programmation - Détective Pikaptcha Ep.1


Introduction

Détective Pikaptcha se trouve dans un labyrinthe, défini par une grille possédant sur chaque case soit un passage, soit un mur.

Le but est de savoir le nombre de passages connectés à chacune des cases (non mur) du labyrinthe.

Approche utilisée

Description synoptique

Mon apprcohe a été de parcourir toutes les cases du labyrinthe, si la case n'est pas un mur, on compte les cases libres adjacentes et on affiche ce nombre. Si la case est un mur on ne fait rien

Algorithme

Grille : tableau de caractères en 2 dimensions
Pour chaque case de la grille : Fin pour

Afficher toute la grille

Résolution


        #include <stdlib.h>
        #include <stdio.h>
        #include <string.h>
        
        // Compte le nombre de cellules non mur autour de la cellule (x, y)
        int check(char grid[256][256], int y, int x, int width, int height) {
            int nb = 0;
            // Check respectivement à gauche, droite, haut, bas 
            nb += (x >= 1 && grid[y][x-1] != '#');
            nb += (x < width-1 && grid[y][x+1] != '#');
            nb += (y >= 1 && grid[y-1][x] != '#');
            nb += (y < height-1 && grid[y+1][x] != '#');
            return nb;
        }
        
        
        int main()
        {
            int width;
            int height;
            scanf("%d%d", &width, &height);
        
            char grid[256][256];
        
            // On stocke la grille donnée en entrée
            for (int i = 0; i < height; i++) {
                char line[256];
                scanf("%s", line);
                strcpy(grid[i], line);
            }
        
            // On parcourt chaque cellule de la grille
            for (int i = 0; i < height; i++) {
                for (int j=0; j<width; ++j) {
                    if (grid[i][j] == '#') {
                        // On skip si c'est un mur
                        printf("#");
                        continue;
                    }
                    printf("%c", '0' + check(grid, i, j, width, height));
                }
                printf("\n");
            }
        
            return 0;
        }
    

Comparaison avec une autre solution

A partir de cette solution externe :

        #include <stdlib.h>
        #include <stdio.h>
        #include <string.h>
        #include <stdbool.h>
        
        int main()
        {
            int width;
            int height;
            int i, j;
            char line[256];
            char prec_line[256] = "";
            scanf("%d%d", &width, &height);
            for (i = 0; i < height; i++) {
                scanf("%s", line);
                for (j=0; j<width; j++){
                  if (line[j] != '#'){
                    if (j != 0 && line[j-1] != '#'){
                      ++line[j];
                      ++line[j-1];
                    }
                    if (i != 0 && prec_line[j] != '#'){
                      ++prec_line[j];
                      ++line[j];
                    }
                  }
                }
                if (i != 0){
                  printf("%s\n", prec_line);
                }
                memcpy(prec_line, line, sizeof(prec_line));
            }
            printf("%s\n", line);
        
            return 0;
        }
        

Cette solution parcrours la grille et incrémente au fur et à mesure les cases voisines. C'est pour ca que j'ai aimé cette solution, qui utilise une logique différente de la mienne, à laquelle je n'avais pas pensé.

Bilan

Après avoir analyser le problème, je l’ai trouvé plutôt simple à résoudre et je n’ai pas rencontré de difficultés.