====== Solution d'un labyrinthe ======

===== Données =====

On vous fournit un labyrinthe sous forme d'un fichier texte.
  * Les murs sont symbolisés par le caractère ''%%*%%'',
  * le point de départ, qui doit être unique, est symbolisé par le caractère ''%%D%%'',
  * les arrivées (il en faut au moins une) sont symbolisées par le caractère ''%%A%%''.

Voici un exemple :

<code lang-none>
*******************
*D*          *A   *
* ******** ****** *
*                 *
*******************
</code>

Vous pouvez télécharger {{ .:laby_exemple.txt |}} dont le contenu est :

<code lang-none>
****************************************************************************************
*         *                                    ** *                                    *
**** ****** **********************************    * * *******************************  *
* *         *                                * ****** *                                *
* * **** **** ****************************** * *      * ******* ************** ******* *
* * * *     * *   *                  *     * * * ****** *   * * *   **       * *     * *
*   * * **  *   *   * ************** *  **** * *      *   *   *   ***  ***** * * ***   *
***** * *   * *********  * *         *       * ****** * *********** ** *   * * *     * *
*     * * *** *          *   ************  *** *      * *            * * *   * ******* *
* ***** * *   *       ********     *       *   * * ** * * ********** * ******* *       *
*       * * *** *******      * *** * ******* *** ***  * * *        * * * *   * * * *****
********* * *   *     * **** * * * *       *       **** * * ****** * *   * * *   * *   *
*   *   *     ******* * *  * * *   ** **** ******* *    * * *    * * * * * * *** * * * *
* * * * *******   *   * * ** * * ******* * *     * * **** * * ** * * * * * *     * * * *
* * * * *     * *   *   *    * *         * * *** * * *  * * * *A * * * * * * * * *   * *
* *   * * ***** ************** *********** * * * * * *  * * * **** * * * * * * * ***** *
* ***** *  *                             * * *   * * *  * * *      * * * * * * *       *
*       ** * *************************** * * ***** * *  * * ******** * * * * * * *******
*** *****  * *   *   *           *       * *       *    * *          * *   *   *       *
*D  *   **** * * * * * ********* ********* ************ * ******************************
*** * * *    * * * *    *                * *        *   *                              *
* * * * * **** * * ****** ************** * ******** * * ****************************** *
* * * * *    * *        *              * * *        * *           *             *      *
* * * * * * ** ******** ************** * * * ******** *********** * * *********** ******
*     *   *             *              *   *                    *   *                  *
****************************************************************************************
</code>


===== Objectif =====

Produire un fichier texte contenant le labyrinthe et sa solution. La solution est affichée en utilisant le caractère ''%%.%%'' pour marquer les cases du chemin à suivre.

Voici un exemple :

<code lang-none>
*******************
*D*          *A...*
*.******** ******.*
*.................*
*******************
</code>

===== Aide =====

==== Ouverture de fichier ====

<code python>
file = open('le_nom_du_fichier_source', 'r', encoding='utf8')
# 'r': ouverture en mode lecture
# 'utf8': précise l'encodage des caractères.
#         inutile ici car aucun caractère spécial.

texte = file.read() # texte contient la totalité du contenu du fichier

# autre possibilité :
lines = file.readlines() # lines contient un tableau dont chaque item est une ligne du fichier

file.close() # ne pas oublier de libérer le fichier
</code>

Vous pouvez ensuite poursuivre en travaillant sur ''%%texte%%'' ou sur ''%%lines%%'' selon le choix fait.

==== Écriture du fichier ====

En supposant que la variable ''%%texte%%'' contient le texte à écrire dans le fichier,

<code python>
file = open('le_nom_de_fichier_cible', 'w', encoding='utf8')
# 'w': écriture
file.write(texte)
file.close()
</code>

==== Méthode ====

Une possibilité est de créer un arbre :
  * Le point de départ est la racine de l'arbre,
  * chaque fois qu'on analyse un nœud, on considère toutes les cellules voisines non encore visitées que l'on ajoute comme enfant du nœud en cours,
  * à partir du nœud racine on fait un parcours en largeur ou en profondeur -- à vous de voir lequel est le mieux
  * quand on visite la cellule d'arrivée, il suffit de remonter l'arbre jusque la racine : c'est le bon chemin.

===== Des améliorations ====

On peut ajouter des complications :
  * Tenir compte d'un temps de parcours qui peut varier selon les cellules, par exemple des cellules pourraient être plus difficiles à parcourir et occasionner une pénalité. On pourrait choisir un symbole pour de telles cellules.
  * Certains passages pourraient être en sens unique.
  * Le labyrinthe pourrait se décomposer en plusieurs étages avec des ascenseurs entre les étages.
  * On peut donner au labyrinthe une représentation graphique dans un module comme tkInter.