Pacman - Sortir en toute sécurité
Vous jouez au jeu Pacman. Vous vous trouvez dans un labyrinthe en compagnie de quelques monstres. Votre objectif est d’atteindre l’une des cases en bordure du labyrinthe, sans jamais partager la même case qu’un monstre.
À chaque tour, vous choisissez une direction (haut, gauche, droite ou bas) pour vous déplacer, et les monstres se déplacent également dans une direction.
S’il est possible de quitter le labyrinthe sans être capturé, vous devez afficher un chemin permettant de réussir. La stratégie doit fonctionner même si les monstres connaissent vos intentions.
Entrée
La première ligne de l’entrée contient deux entiers
h et w (1 ≤ h, w ≤ 1000), qui représentent la hauteur et la largeur du labyrinthe.Les
h lignes suivantes contiennent w symboles décrivant le labyrinthe:.- sol
#- mur
M- monstre
Y- votre position initiale
Sortie
La première ligne de la sortie doit contenir le nombre de pas nécessaires pour sortir du labyrinthe, ou
Impossible s’il n’existe aucun moyen d’y parvenir.Si vous pouvez effectivement sortir, la ligne suivante doit indiquer un chemin valide pour y arriver.
Exemples
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB