← 返回题目列表

AtCoder · kupc2018_b

B. 弹幕地狱游戏

中文机器翻译题面 查看原题

配点 : 200 点

問題文

您正在玩某种弹幕地狱游戏。

您的目标是通过正确操作飞机来避免被击中,哪怕只有一次。

这个弹幕地狱游戏的地图是 H 行 W 它由列网格表示。

在游戏开始时您会获得地图的状态。

i 行 j 列方块中的文本 写入 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