Danse pressée – Épreuve régionale 2004

Énoncé¶

Vous êtes au gala de fin d'année de votre école. Ambiance de folie, musique qui déchire, jolies filles, beaux mecs, etc. Bref, une soirée de rêve. Mais tout à coup, un besoin pressant vous ramène à des considérations bassement matérielles : atteindre les toilettes le plus vite possible !

Bien sûr, vous ne voulez pas trop vous faire remarquer en fonçant directement vers les toilettes, et pour ne pas dégrader l'ambiance, vous décidez d'y aller en dansant. Vous avez un répertoire limité de pas de danse, et vous devez puiser dans ce répertoire, en enchaînant les pas, pour atteindre les toilettes élégamment, tout en évitant les divers obstacles placés sur la piste : poteaux, couples enlacés, enceintes, etc.

On vous décrit la piste de danse et ses obstacles, sous la forme d'un tableau à deux dimensions, rempli de caractères. Les '.' représentent des zones libres, et les '#' représentent des obstacles, donc des zones sur lesquelles vous ne pouvez pas dancer.

Vous partez de la première colonne de la première ligne, et devez atteindre la sortie, sur la dernière colonne de la dernière ligne.

On vous décrit également la liste des pas de danse disponibles. Un pas de danse est décrit sous la forme d'une succession de déplacements, dans les quatre directions : gauche (G), droite (D), haut (H), bas (B).

Le sujet se décompose en deux parties. Dans la première partie, on vous demande simplement d'indiquer le nombre de pas de danse utilisés. Dans la deuxième, on vous demande de lister ces pas de danse.

Si vous ne faites que la première partie, vous n'obtiendrez que la moitié des points pour ce problème, et ne pourrez pas passer au problème suivant.

Dans la deuxième partie, s'il existe plusieurs chemins, vous devez fournir celui qui commence en priorité par les pas de danse d'indice les plus faibles.

Entrée¶

Vous devez lire les lignes suivantes sur l'entrée :

• La première ligne contient un entier, qui vaut 0 ou 1 : 0 pour la première partie et 1 pour la partie 2.
• La deuxième ligne contient un entier : le nombre de pas de danse $N$ de votre répertoire.
• Les $N$ paires de lignes suivantes décrivent les pas de danse disponibles :
  • La première ligne de chaque paire contient un entier : le nombre $E$ d'étapes du pas de danse.
  • La deuxième ligne contient $E$ caractères : les étapes du pas de danse.
• La ligne suivante contient deux entiers séparés par une espace : le nombre $L$ de lignes du tableau puis le nombre de $C$ colonnes.
• Les $L$ lignes suivantes contiennent chacune $C$ caractères décrivant la piste.

Sortie¶

Si on ne vous demande de faire que la partie 1, vous devez écrire une ligne sur la sortie, contenant un entier $P$ : le nombre minimum de pas de danse à effectuer pour sortir du labyrinthe.

Dans le cas de la partie 2, vous devez écrire une deuxième ligne, décrivant les différents pas de danse à effectuer, sous la forme d'une suite de numéros de pas de danse, séparés par des espaces.

Le premier pas de danse fourni dans l'entrée correspond au pas n°1.

Contraintes¶

• $1 \le P \le 255$
• $1 \le E \le 255$
• $1 \le L, C \le 1\,000$