Atomes – Épreuve régionale 2004

É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, 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.

Une glissade de plusieurs cases dans une direction est considérée comme une seule étape.

Contraintes¶

• $1 \le C, L \le 1\,000$