B - 弾幕ゲーム Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200200

問題文

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

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

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

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

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

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

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

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

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

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

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

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

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

制約

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

入力

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

HH WW
c11...c1Wc_{11}...c_{1W}
c21...c2Wc_{21}...c_{2W}
::
cH1...cHWc_{H1}...c_{HW}

出力

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

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


入力例1Copy

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

出力例1Copy

Copy
LRR

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

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

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


入力例2Copy

Copy
3 3
xxx
...
.s.

出力例2Copy

Copy
impossible

入力例3Copy

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

出力例3Copy

Copy
RSLLR


2025-03-13 (Thu)
21:54:09 +00:00