16 · Welcome24ever 和火车游戏

题目描述

移动应用商店上线了一款新游戏，叫做 “Subway Roller”。 游戏的主角 Welcome24ever 位于隧道的一端，想要穿越到另一端。隧道是一个由三行 $n$ 列组成的矩形区域。游戏开始时，主角出现在最左侧列的某个单元格中。有若干列火车正朝着主角驶来。每辆火车在该区域的某一行上，由两个或更多相邻单元格组成。 所有火车以每秒两格的速度从右向左移动，而主角每秒以一格的速度从左向右奔跑。为简化实现，游戏规定主角和火车轮流移动： 首先，主角向右移动一格，然后可以选择向上或向下移动一格，或保持在当前行不动； 接着，所有火车会同时向左移动两格。 因此，在一次操作中，Welcome24ever 一定会向右移动一列，并且可以选择向上、向下或不变。如果在任意时刻 Welcome24ever 与火车处于同一个格子，他就会失败。如果火车到达最左侧列，它仍然会像之前一样继续移动，最终驶出隧道。 你的任务是判断：是否存在一系列移动方式，使得 Welcome24ever 能够在不与任何火车相撞的前提下，成功到达最右侧的一列。

每个测试包含一到十组数据。 第一行包含一个整数 $t$（ $1 \le t \le 10$）——测试数据组数。 接下来是 $t$ 组数据，每组数据的格式如下： 第一行包含两个整数 $n, k$（$2 \le n \le 100$，$1 \le k \le 26$），分别表示隧道的列数以及火车的数量。 接下来三行，每行包含一个长度为 $n$ 的字符串，表示隧道中一行的布局： 字符 's' 表示 Welcome24ever 的初始位置，且一定在最左侧列（第 $1$ 列）的某一行； 每辆火车用某个大写英文字母在某一行连续标记（长度至少为 $2$），不同火车用不同的大写字母； 字符 '.' 表示该格为空（既没有主角也没有火车）。

对于每组数据，如果 Welcome24ever 能够成功到达最右侧一列，则输出一行： YES 否则输出： NO

输入 #1

2
16 4
...AAAAA........
s.BBB......CCCCC
........DDDDD...
16 4
...AAAAA........
s.BBB....CCCCC..
.......DDDDD....

输出 #1

YES
NO

输入 #2

2
10 4
s.ZZ......
.....AAABB
.YYYYYY...
10 4
s.ZZ......
....AAAABB
.YYYYYY...

输出 #2

YES
NO