分数: 700 点
问题陈述
我们有一个网格 N 行和 M 列。 您想在之间写入一个整数 0 和 2^K-1 网格中的每个方格满足以下条件。
- 考虑一条从左上角的方块开始,反复向右或向下移动到相邻方块,并在右下角的方块结束的路径。 据说这样的路径是 好 当且仅当总计 所访问的方格上所写的整数(包括起点和终点)的 \mathrm{XOR} 为 0.
- 正好有一个好路径,就是用字符串表示的路径 S。
字符串表示的路径 S 是一条路径,对于每个 i (1 \leq i \leq N+M-2), i- 第一步棋是正确的,如果 i- 第一个字符 S is
R并向下,如果该字符是D.
判断是否有办法写入满足条件的整数。
对于每个输入文件,求解 T 测试用例。
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B定义如下。
- 当 A \oplus B 以二进制形式写入, k- 第最低位 (k \geq 0) 是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),可以证明与顺序无关 p_1, p_2, p_3, \dots, p_k.
约束
- 1 \leq T \leq 100
- 2 \leq N,M \leq 30
- 1 \leq K \leq 30
- S 是一个字符串,恰好包含 N-1
D和 M-1Rs。 - 输入中的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例的格式如下:
N M K S
输出
对于每种情况,打印 Yes 如果有一种方法可以写入满足条件的整数,并且 No 否则。
输出中的每个字符可以是大写或小写。
示例输入 1
4 2 2 1 RD 4 3 1 RDDDR 15 20 18 DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR 20 15 7 DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD
示例输出 1
Yes No Yes No
例如,对于第一种情况,您可以按如下方式制作网格。
11 00