Kyoto University Programming Contest 2018

B - 弾幕ゲーム


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 200

問題文

あなたはとある弾幕ゲームで遊んでいます。

あなたの目的は、適切に自機を操作することで一度も被弾しないことです。

この弾幕ゲームのマップは HW 列のマス目で表現されています。

あなたにはゲーム開始時点でのマップの状態が与えられます。

ij 列目のマスには文字 c_{ij} が書かれており、c_{ij} は以下のいずれかです。

  • . の場合:何もないマス。
  • x の場合:弾を表すマス。
  • s の場合:自機を表すマス。マップの一番下の行にただ 1 つだけ存在する。

自機および弾の移動は、ゲーム開始から t (1 \leq t \leq H - 1) 秒後に同時かつ瞬時に行われます。移動後に自機と弾が同じマスに存在する場合は、被弾となります。

それぞれの弾は、移動ごとに 1 つ下のマスへ移動します。そして一度マップ外に出た弾は消滅し、以降ゲームに現れることはありません。

自機の移動は、あらかじめ命令列を出力することによって行います。

命令列は H - 1 文字からなる文字列で、i 文字目はゲーム開始から i 秒後の自機の移動を表します。このとき、各文字は以下のいずれかでなければなりません。

  • L:左に 1 マス移動する。
  • R:右に 1 マス移動する。
  • S:そのマスにとどまる。

ただし、ゲームの途中で自機が画面外に出るような命令列は与えることができません。

目的を達成できる命令列が存在するならば、そのうちの 1 つを出力してください。存在しないならば、impossible を出力してください。

制約

  • 2 \leq H, W \leq 10
  • c_{ij}., x, s のいずれかである。
  • 自機は必ず一番下の行のマスのいずれかにただ 1 つ存在する。

入力

入力は以下の形式で標準入力から与えられる。

H W
c_{11}...c_{1W}
c_{21}...c_{2W}
:
c_{H1}...c_{HW}

出力

目的を達成できる命令列が存在するならば、そのうちの 1 つ(いずれでもよい)を一行で出力せよ。存在しないならば impossible を出力せよ。

出力の末尾には改行を入れること。


入力例1

4 3
xx.
...
.xx
.s.

出力例1

LRR

この命令列に従って自機を移動させると、以下のようになります。

xx.        ...        ...        ...
...   L    xx.   R    ...   R    ...
.xx  --->  ...  --->  xx.  --->  ...
.s.        sxx        .s.        xxs

この入力では、LRR が唯一達成可能な命令列となります。


入力例2

3 3
xxx
...
.s.

出力例2

impossible

入力例3

6 4
x.xx
.xxx
x.xx
xx.x
xx.x
.s..

出力例3

RSLLR

Submit提出する