← 返回题目列表

AtCoder · agc060_b

B. 独特的异或路径

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \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-1 Rs。
  • 输入中的所有数字均为整数。

输入

输入由标准输入按以下格式给出:

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