#E. 光束

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给你一个 $n \times m$ 的字符矩阵，其中"L"代表了光束的开始位置。

（光束总是先向右投射出去）

"W,A,S,D"分别代表一面镜子，光束会因为镜子的折射向"上，左，下，右"传播。

镜子只要反射过光束都会被销毁（即镜子只能反射一次光束）。

"_,X"分别代表"空地，墙壁"。

求出光束最终停下来的位置。（光束移出边界也算停下来）

第一行，两个正整数 $n, m$ 。

第二行至第 $n + 1$ 行，每行 $m$ 个字符，描述这个矩阵。

一行，两个正整数，表示光束最终停下来的位置。

5 5
__L_S
_SA__
__W_A
_____
_D_W_

1 4

对于 $100\%$ 的数据， $n,m \le 5000$