U213465 [GDOI2022 普及组] 机器人

刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 $n\times m$ 的网格图，行从上往下标号为 $1,\cdots,n$，列从左往右标号为 $1,\cdots,m$。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用 `.`、`*`、`R` 表示。现在小纯需要控制机器人在考试场地上行走，她每秒可以发送一条指令，为 `W`——往上走、`S`——往下走、`A`——往左走、`D`——往右走的其中之一。由于俱乐部的机器人是避障机器人，当机器人接收到一条指令的时候，如果即将到达的位置为障碍物，那么机器人将留在原地，否则机器人向对应方向走一步。如果其走出边界则考试失败（例如在第一行发送指令向上走）。 为了增加考试的难度，俱乐部提供的机器人的信号接收器都存在问题。换言之，对于小纯给出的每一条指令，机器人有可能接收到指令并执行，也有可能接收不到指令并保持不动。 现在小纯提供了一个指令序列，她想知道，这个指令序列是否存在某些情况使得这个指令序列走出边界。

每个测试点包含多组数据。 第一行一个正整数 $T$，表示数据组数。 对于每组数据： 第一行一个由 `W`，`A`，`S`，`D` 组成的字符串 $S$，表示小纯的指令序列。 第二行两个正整数 $n,m$ 表示考试场地的长度和宽度。 接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述考试场地。

对于每组数据，输出一行。`YES` 表示可能走出考试场地，`NO` 表示不可能走出场地。

令 $\lvert S\rvert$ 表示指令序列长度。对于所有测试点，$1\leq T\leq 10$，$1\leq \lvert S\rvert \leq 10^5$，$1\leq n,m\leq 500$。 |测试点|$T\leq$|$\lvert S\rvert\leq$|$n,m\leq$| |:-:|:-:|:-:|:-:| |$1\sim 4$|$\leq 10$|$\leq 15$|$\leq 10$| |$5\sim 6$|$\leq 10$|$\leq 50$|$\leq 50$| |$7\sim 10$|$\leq 10$|$\leq 1000$|$\leq 50$| |$11\sim 14$|$\leq 10$|$\leq 10^5$|$\leq 70$| |$15\sim 20$|$\leq 10$|$\leq 10^5$|$\leq 500$|