Page web ISIMA Fichier .html source

SCHIRRA Rémi Prep ISIMA 1 - 2023-2024

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


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 parcourir le labyrinthe en suivant le mur à gauche ou droite, jusqu'à ce que l'on retombe sur la case de départ, et de tenir le compte du nombre de fois où on est passé sur chaque case.

Approche utilisée

Description synoptique

Mon approche a été de faire avancer le détective dans le labyrithne, tout en suivant le mur à droite ou à gauche, et d'ajouter 1 à la valeur de chaque case par laquelle on passe.

Algorithme

newDir : Fonction déterminant la nouvelle direction de Pikachu, en fonction de sa direction actuelle et si il doit suivre le mur gauche ou droit

isSideClear : Fonction déterminant si la case à gauche ou droite (en fonction du mur à suivre) est libre ou non

newX : Fonction déterminant la nouvelle position X de Pikachu en fonction de sa direction

newY : Fonction déterminant la nouvelle position Y de Pikachu en fonction de sa direction

Grille : tableau de caractères en 2 dimensions
Dir : la direction de pikatchu, de 0 à 3, respectivement haut, droite, bas, gauche
X : la position horizontale de pikatchu dans la grille
Y : la position verticale de Pikatchu dans la grille
startX : la position horizontale de départ de Pikachu
startY : la position verticale de départ de Pikachu

Pour chaque case de la grille :

Fin pour
Boucle de 0 à 4 (exclu) : Fin boucle

Tant que Pikachu n'est pas sur la case de départ (x != startX ou y != startY) :

Fin boucle

Afficher toute la grille

Résolution


        #include <stdlib.h>
        #include <stdio.h>
        #include <string.h>
        #include <stdbool.h>
        
        // Renvoie vrai si la cellule vérifiée est un mur ou a l'extérieur de la grille
        int isWall(char grid[256][256], int x, int y, int width, int height) {
            return grid[y][x] == '#' || x<0 || x>= width || y<0 || y>= height;
        }
        
        // Renvoie vrai si il n'y a aucun mur sur la droite ou gauche du pikachu
        int isSideClear(char grid[256][256], int x, int y, int dir, char side, int width, int height) {
            int xPoses[4] = {1, 0, -1, 0};
            int yPoses[4] = {0, -1, 0, 1};
            int mult = (side == 'R') ? 1 : -1;
            int xPos = xPoses[dir] * mult + x;
            int yPos = yPoses[dir] * mult + y;
            return !isWall(grid, xPos, yPos, width, height); 
        }
        
        int newX(int x, int dir, char side) {
            int xPoses[4] = {0, 1, 0, -1};
            int mult = (side == 'R') ? 1 : -1;
            return xPoses[dir] + x;
        }
        int newY(int y, int dir, char side) {
            int yPoses[4] = {1, 0, -1, 0};
            int mult = (side == 'R') ? 1 : -1;
            return yPoses[dir] + y;
        }
        int newDir(int dir, char side, int mult) {
            int a = (side == 'R') ? 1 : -1;
            int b = (dir + a*mult) % 4;
            return (b<0) ? 4+b : b;
        }
        
        int main()
        {
            int width;
            int height;
            int x, y, startX, startY;
            int dir = -1; // 0 1 2 3, up right down left
            char grid[256][256];
        
            scanf("%d%d", &width, &height);
            for (int i = 0; i < height; i++) {
                char line[256];
                scanf("%s", line);
                strcpy(grid[i], line);
                for(int j=0; j<256; ++j) {
                    // Cherche la position et direction de départ
                    if (line[j]=='^' || line[j]=='>' || line[j]=='v' || line[j]=='<') {
                        switch (line[j]) {
                            case '^' : dir = 0; break;
                            case '>' : dir = 1; break;
                            case 'v' : dir = 2; break;
                            case '<' : dir = 3; break;
                        }
                        x = startX = j;
                        y = startY = i;
                        grid[i][j] = '0';
                        //printf("%d, %d, %d, %c\n", x, y, dir, line[j]);
                    }
                }
            }
            char side;
            scanf(" %c", &side);
            
            // Essaye de sortir de la case de départ
            for (int i=0; i<4; ++i) {
                int posX = newX(x, dir, side);
                int posY = newY(y, (dir+2)%4, side);
                if (!isWall(grid, posX, posY, width, height)) {
                    x = posX;
                    y = posY;
                    grid[y][x] += 1;
                    break;
                }
                dir = newDir(dir, side, 1);
            }
            
            while (x != startX || y != startY) {
                if (isSideClear(grid, x, y, dir, side, width, height)) {
                    dir = newDir(dir, side, 1);
                    x = newX(x, dir, side);
                    y = newY(y, dir, side);
                    grid[y][x] += 1;
                } else {
                    dir = newDir(dir, side, -1);
                }
            }
        
            // Affiche la grille résultante
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    printf("%c", grid[i][j]);
                }
                printf("\n");
            }
        
            return 0;
        }
        

Comparaison avec une autre solution

A partir de cette solution externe :

        #include <stdio.h>
        
        typedef unsigned char uint8;
        
        _Bool forward_grid(uint8 grid[][101], uint8 width, uint8 height, uint8 *X, uint8 *Y, uint8 r) {
            uint8 x = *X + (r - 1) % 2, y = *Y + (2 - r) % 2;
            if (x >= height || y >= width || grid[x][y] == '#') return 0;
            *X = x, *Y = y;
            return 1;
        }
        
        int main() {
            uint8 width, height, X = 0xff, Y, R, side, cX, cY, i;
            scanf("%hhd%hhd", &width, &height);
        
            uint8 grid[height][101]; // 100 because max(width) == 100 + '\0'
        
            for (uint8 i = 0; i < height; i++) {
                scanf("%s", grid[i]);
                if (X == 0xff) for (uint8 u = 0; u < width; u++) switch(grid[i][u]) {
                    case '^': R = 0, X = i, Y = u; break;
                    case '>': R = 1, X = i, Y = u; break;
                    case 'v': R = 2, X = i, Y = u; break;
                    case '<': R = 3, X = i, Y = u; break;
                }
            }
            scanf("%c%c", &side, &side); // 2 times because "\nR" / "\nL"
            
            grid[cX = X][cY = Y] = '0', side = side == 'R' ? 1 : 0xff; // Recycling to a rot. coeff : 1 = R, 0xff = -1 = L
            
            do {
                for (i = 0; i < 4 && !forward_grid(grid, width, height, &cX, &cY, R = (uint8)(R + side) % 4); i++) R = (R + 2) % 4;
                if (i < 4) grid[cX][cY]++;
            } while (cX != X || cY != Y);
        
            for (uint8 i = 0; i < height; i++) printf("%s\n", grid[i]);
        
            return 0;
        }
    
La logique pour gérer les positions, rotations et récupération des entrées est la même que la mienne.
Néanmoins, au lieu de vérifier si la case sur le côté de Pikachu est libre, cette solution propose de vérifier celle de devant, et de tourner si la case est un mur.
J'ai aimé dans cette solution la manière dont les positions sont mises à jour en fonction de la direction de Pikachu.

Bilan

J'ai trouvé la méthode à suivre pour résoudre le problème assez rapidement, mais l'implémenter a été plus dur et m'a demandé beaucoup de temps.
J'ai eu des difficultés pour faire sortir Pikachu de sa case de départ avant qu'il ne parcoure le labyrinthe.