配点 : 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