Rapport sur Le Labyrinthe

1. présentation du problème
2. méthode de résolution
- 2.1. détail algorithmique
- 2.2. code de résolution
3. tests
4. conclusion

1. présentation du problème

Le labyrinthe est un problème du site codingame, c’est un exercice ou il faut trouver le meilleur chemin dans un labyrinthe pour relier 2 points, la position de départ à la salle de commande tout cela en trouvant le chemin le plus cours possible car un compteur est lancé au moment ou on atteint la salle de commande, et si on n’a pas le chemin le plus cours Rick echouera. Il faut utiliser l’algorithme djikstra pour résoudre ce problème, c’est un algorithme qui ressemble à celui du parcours en largeur. Il va nous permettre de trouver le plus cours chemin entre la position initiale et la salle de commande. On nous donne en entrées 3 valeurs, R,C et A, qui correspondent aux nombres de lignes, nombres de colonnes et le nombre initiale du compte à rebours. On nous donne ensuite chaque tour 2 entiers, KR et KC qui correspondent au coordonées de Rick, KR pour la ligne et KC pour la colonne et on nous donne ensuite le labyrinthe représentés avec des ’#’ pour les murs, des ’.’ pour les passages, un ’T’ pour la position initiale de Rick, un ’C’ pour la position de la salle de commande, ainsi que des ’?’ pour les zones pas encore décourvertes.

2. méthode de résolution

2.1. détail algorithmique

n’ayant pas réussi cet exercice, j’ai essayer de creer un détail algorithmique assez simpliste mais je pense “fonctionnel”.

2.2. code de résolution

voici le morceau de code creer, je pense ne pas avoir bien compris le mode de fonctionnement des algorithmes de parcours de graph, cela demande des recherches et essais plus poussés, ce que je n’ai plus le temps de faire.

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


int main()
{
    // number of rows.
    int R;
    // number of columns.
    int C;
    // number of rounds between the time the alarm countdown is activated and the time the alarm goes off.
    int A;
    scanf("%d%d%d", &R, &C, &A);

    char grille[1000][1000];
    bool trouve=false;

    // game loop
    while (1) {
        // row where Rick is located.
        int KR;
        // column where Rick is located.
        int KC;
        scanf("%d%d", &KR, &KC);
        for (int i = 0; i < R; i++) {
            // C of the characters in '#.TC?' (i.e. one line of the ASCII maze).
            char ROW[C + 1];
            scanf("%s", ROW);

            for (int j = 0; j < C; j++) {
                grille[i][j]=ROW[j];
            }
        }

        // Write an action using printf(). DON'T FORGET THE TRAILING \n
        // To debug: fprintf(stderr, "Debug messages...\n");
        if (trouve==false){
            if(grille[KR][KC+1]!='#'){
                if(grille[KR][KC+1]=='C'){
                    trouve=true;
                }
                printf("RIGHT\n");
            }               
            else if(grille[KR+1][KC]!='#'){
                if(grille[KR+1][KC]=='C'){
                    trouve=true;
                }
                printf("DOWN\n");
            }
            else if(grille[KR][KC-1]!='#'){
                if(grille[KR][KC-1]=='C'){
                    trouve=true;
                }
                printf("LEFT\n");
            }
            else if(grille[KR-1][KC]!='#'){
                if(grille[KR-1][KC]=='C'){
                    trouve=true;
                }
                printf("UP\n");
            }
        } else{
            if(grille[KR][KC-1]!='#'){
                printf("LEFT\n");
            }
            else if(grille[KR-1][KC]!='#'){
                printf("UP\n");
            }
            else if(grille[KR][KC+1]!='#'){
                printf("RIGHT\n");
            }               
            else if(grille[KR+1][KC]!='#'){
                printf("DOWN\n");
            }
        }
    }

    return 0;
}

3. tests

Les code n’etant pas fonctionnel et les tests n’etant pas “fixe” le chargement de la grille se fait en fonction de la direction indiquée a chaque tour, je ne peut fournir des tests.

4. conclusion

Cet exercice est un échec et demande d’y repasser du temps afin de comprendre les algorithmes de parcours en largeur.

Vous pouvez retrouver ce rapport sur ma page personnelle