Atomes – Regional event 2004

Level 5

Énoncé

Le labyrinthe est un tableau de caractères à deux dimensions. Les murs sont représentés par des '#', et les zones libres par des '.'. Lorsque l'on commence à se déplacer dans ce labyrinthe, dans une direction, on glisse sans pouvoir s'arrêter, dans cette direction, jusqu'à rencontrer un mur, les limites du terrain, ou la sortie. On peut ensuite repartir dans une autre direction, et glisser de nouveau. (Si vous connaissez le jeu "atomes", ce sont les mêmes règles de déplacement)

Par exemple :

1
2
3
4
5
6
7
Ce mouvement est possible       Celui-là ne l'est pas

#.##################            #.##################
#X+++++++++++++++++#            #X++++++++.........#
#########.########+#            #########+########.#
........#.........Y.            ........#+++++++++Y.
........###########.            ........###########.

Vous devez écrire une fonction qui détermine le plus court chemin permettant de sortir du labyrinthe. L'itinéraire commence à la case située sur la première colonne de la première ligne du tableau et doit arriver à la case située sur la dernière colonne de la dernière ligne.

Le plus court chemin est unique dans tous les tests.

Le sujet est décomposé en deux parties. La première partie consiste à indiquer le nombre d'étapes de l'itinéraire (une glissade de plusieurs cases dans une direction est considérée comme une étape), et la deuxième partie consiste à indiquer les directions de ces différentes étapes.

Si vous ne faites que la première partie, vous obtiendrez 50% des points pour ce problème, et ne pourrez pas passer à la suite. (la moitié des fichiers tests sont consacrés à chaque partie)

Éntrée

La première ligne de l'entrée contient un entier, qui vaut 0 ou 1, respectivement si on vous demande d'effectuer la première ou la deuxième partie pour le test.

La deuxième ligne de l'entrée contient deux entiers, séparés par un espace : le nombre de lignes L, et le nombre de colonnes C du labyrinthe.

Chacune des L lignes suivantes contient C caractères, '.' ou '#', décrivant une ligne du labyrinthe.

Sortie

Si on vous demande de faire la première partie, vous devez afficher une ligne sur la sortie, contenant un entier : le nombre d'étapes du chemin.

Si on vous demande de faire la deuxième partie, vous devez afficher également, sur la deuxième ligne, une chaîne de caractères contenant le chemin (G = gauche, D = droite, H = haut, B = bas), dans l'ordre.

Contraintes

  • 1 <= C, L <= 1000, où C et L sont respectivement le nombre de colonnes et le nombre de lignes du labyrinthe.

Runtime constraints

Maximum memory usage
16000 kilobytes
Maximum execution time
2500 milliseconds

Input/output samples

Sample input
0
10 20
.###################
.###################
.###########......##
.###########.####.##
.............####.##
####.#######.####.##
####.#######.####.##
####.############.##
####.........####.##
############........
Sample output
6
Sample input
1
10 20
.###################
.###################
.###########......##
.###########.####.##
.............####.##
####.#######.####.##
####.#######.####.##
####.############.##
####.........####.##
############........
Sample output
6
BDHDBD

Submit your solution

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