Trouver la sortie dans un labyrinthe

Le labyrinthe

Un labyrinthe est un graphe non orienté: chaque carrefour est un noeud du graphe, chaque chemin est un arc. La sortie d'un labyrinthe peut se trouver par un simple parcours de graphe à partir de l'entrée jusqu'à atteindre une sortie.

Un simple parcours en profondeur convient. pour pouvoir une fois la sortie trouvée reconstruire le chemin qui évite les culs-de-sac, il faut en plus garder un fil d'ariane qui permet de remonter directement de la sortie vers l'entrée (rechercher ses amis et les sauver). Pour cela on garde pour chaque carrefour (noeud) un pointeur arrière vers le carrefour d'où l'on vient.

Le plus court chemin peut être trouvé de façon similaire par un parcours du graphe en largeur ou plus généralement avec une file de priorité.

La structure de donnée

On choisit un labyrinthe plan représenté par les cases noires et blanches d'un damier carré. Une case est un sommet et deux cases blanches adjacentes définissent un arc.

Concrètement, on pourra dessiner le labyrinthe comme un damier, et le construire en en cliquant sur les cases noires à blanchir. Pour éviter les cas particuliers aux bords, on pourra simplement imposer que les bords du damier restent toujours noires.

Par contre il est plus commode de calculer sur une structure de graphe régulière (simple tableau de sommets). Ce que l'on réalise facilement en numérotant les cases. Le labyrinthe est donc représenté par un tableau de S cases contigües noires ou blanches selon qu'il est possible de se déplacer dessus. L'état d'une case doit être simultanément mémorisé dans le tableau et dessiné à l'écran.

  1. Les états possibles des cases sont 

            typedef enum {Interdit = 0, Depart = 1, Sortie = 2, Libre = 3} Etat;
  2. Écrire la structure de donnée du labyrinthe
  3. Écrire une fonction 

            void change_etat (Sommet x, Etat m)
    qui modifie l'état du noeud x et colorie la case correspondante dans la bonne couleur. (L'utilisation de change_etat garantit la cohérence entre la représentation abstraite et le dessin du labyrinthe).
  4. Écrire une procédure pour construire le labyrinthe en partant de cases noires et en cliquant sur les cases dont on veut changer l'état. (On s'arrête par un clique en bordure ou en dehors).

    On pourra utiliser le fichier graphique.c dont l'interface est graphique.h.

    Il suffit pour cela de copier les deux fichiers dans le dossier courant, d'ajouter 

            #include "graphique.h"
    en entête du programme, et de compiler avec 

            gcc -Wall -o labyrinthe graphique.c labyrinthe.c -lX11 -lMacLib
  5. A un noeud x correspond quatre fils potentiellement possible, que l'on pourra numéroter ainsi: 
                1           
         0  x  2        
            3
    Écrire une fonction 

            Sommet fils (Sommet x, int k);
    qui retourne le k-ième fils du sommet x

L'algorithme

Il sera nécessaire d'annoter les noeuds par un drapeau indiquant si un noeud a déjà été visité. Il faudra aussi maintenir les pointeurs des sommets visités vers leur parent. On peut maintenir ces informations dans deux tableaux annexes séparés.

Recherche du plus court chemin

Le chemin précédent est sans cul-de-sac, mais ce n'est pas le plus court. Pour trouver le chemin le plus court, on pourrait faire un parcours en largeur, mais on gagnera en généralité en utilisant un parcours avec file de priorité. En effet, on pourra alors annoter les cases par la qualité du terrain, indiquant le court de passage sur chaque case.

Solution