Danse pressée – Regional event 2004

Level 5

Énoncé

Vous êtes au gala de fin d'année de votre école. Ambiance de folie, musique qui déchire, jolies filles (ou beaux mecs, pour ceux/celles qui préfèrent), etc. Bref, une soirée de rêve. Mais tout d'un 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 de pas de danse, et vous devez puiser dans le répertoire, en enchaînant les pas, pour atteindre les toilettes élégamment, tout en évitant les divers obstacles placés sur la piste : potaux, 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 espaces représentent des zones libres, et les '#' représentent des obstacles, donc des zones sur lesquelles vous ne pouvez pas passer.

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, droite, avancer, reculer.

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é les pas de danse d'index les plus faibles.

Contraintes

  • 1 <= P <= 255, où P est la longueur d'un pas de danse.
  • 1 <= NP <= 255, où NP est le nombre de pas de danse.
  • 1 <= L, C <= 1000, où L et C est la taille de la piècee en lignes et colonnes.

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 : vous ne devez afficher que le nombre de pas de danse, et 1 pour la partie 2.
  • La deuxième ligne contient un entier : le nombre de pas de danse N.
  • 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 NP d'étapes du pas de danse. La deuxième ligne contient NP caractères : les étapes du pas de danse.
  • La ligne suivante contient deux entiers séparés par un espace: le nombre L de lignes de la matrice puis le nombre de C colonnes.
  • Les L lignes suivantes contiennent chacune C caractères, parmi '.' et '#', 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 pas de danse 1 est le premier fourni dans l'entrée.

Runtime constraints

Maximum memory usage
16000 kilobytes
Maximum execution time
2500 milliseconds

Input/output samples

Sample input
0
4
1
B
1
G
2
DD
1
D
6 5
..#..
#....
..##.
##...
...##
.....
Sample output
11
Sample input
1
4
1
B
1
G
2
DD
1
D
6 5
..#..
#....
..##.
##...
...##
.....
Sample output
11
4 1 3 4 1 1 2 2 1 1 3

Submit your solution

You have to register or log in to be able to submit your solution.