Pacman - Get Out Safely
あなたはPacmanというゲームをプレイしています。迷路のような場所にはモンスターがいます。モンスターと同じマスに入り込まずに、迷路の外周上にあるマスのいずれかまでたどり着く必要があります。
毎回の手番では、あなたが上下左右いずれかの方向へ移動し、モンスターも各自で何らかの方向に動きます。
もし安全に迷路を抜け出せるのであれば、辿ることができる道順を出力してください。モンスターがあなたの計画を知っていたとしても通用する戦略である必要があります。
Input (入力)
最初の行には、迷路の高さと幅を示す2つの整数
h と w (1 ≤ h, w ≤ 1000) が与えられます。続く
h 行には w 文字が書かれており、迷路の構造を示しています:.- 床
#- 壁
M- モンスター
Y- あなたの初期位置
Output (出力)
最初の行には迷路を抜け出すまでに必要な手数を出力します。もし脱出が不可能な場合は
Impossible を出力してください。脱出が可能な場合、その次の行に有効な経路を示す任意のパスを出力してください。
Examples (例)
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB