The Unstoppable Robot
迷路を移動できるロボットを開発している学生たちがいました。しかし、このロボットには欠点があり、いったん動き始めると、壁や障害物にぶつかるまで方向転換や停止ができません。そのため、ロボットが動き始めると、今向いている方向の一番近い壁に到達してから、次の進む方向を選ぶ必要があります。
このロボットが、スタート位置の
S からゴール位置の E まで移動する際に必要な最小の移動回数を求め、そのために送信するコマンド列を出力してください。コマンドは以下のとおりです:- L - 左に進む
- U - 上に進む
- R - 右に進む
- D - 下に進む
Input
入力の最初の行には、グリッドの高さと幅を表す 2 つの数値
h と w (2 ≤ h, w ≤ 100) が与えられます。続く
h 行には、幅 w 文字で構成されるグリッドが与えられます:.は床を表します
#は壁を表します
Sはスタート地点を表します
Eはゴール地点を表します
また、ロボットがグリッドの外に出ないよう、周囲がすべて壁で囲まれていることが保証されています。
Output
プログラムは、スタート地点からゴール地点に到達するまでに必要な最小の移動回数を、最初の行に出力します。続く行には、ロボットに送るコマンド列を出力してください。可能な解答が複数ある場合は、いずれかを出力すれば構いません。
もしゴール地点まで到達できない場合は、
Impossible と出力してください。Examples
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUHint
スタート地点を床 (
.) として扱い、ゴール地点を壁 (#) として扱う方法があります。Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB