Pacman – Sicher entkommen
Du spielst gerade Pacman in einem Labyrinth, in dem sich einige Monster befinden. Dein Ziel ist es, eines der Felder am Rand des Labyrinths zu erreichen, ohne jemals ein Feld mit einem Monster zu teilen.
In jedem Zug bewegst du dich in eine Richtung (nach oben, links, rechts oder unten), und auch die Monster bewegen sich dabei in eine beliebige Richtung.
Falls es möglich ist, sicher aus dem Labyrinth zu entkommen, sollst du den Weg ausgeben, den du gehen kannst.
Input
Die erste Zeile der Eingabe enthält zwei ganze Zahlen h und w (1 ≤ h, w ≤ 1000), also die Höhe und Breite des Labyrinths.
Die nächsten h Zeilen bestehen aus w Symbolen, welche das Labyrinth beschreiben:
- '.' – Boden
- '#' – Wand
- 'M' – Monster
- 'Y' – deine Startposition
Output
Die erste Zeile der Ausgabe sollte die Anzahl der benötigten Schritte enthalten, um aus dem Labyrinth zu entkommen; falls es nicht möglich ist, gib "Impossible" aus.
Wenn ein Entkommen möglich ist, soll die nächste Zeile einen beliebigen gültigen Pfad angeben, der ans Ziel führt.
Examples
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB