/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N 行 M 列のグリッドがあります． あなたはグリッドの各マスに 0 以上 2^K-1 以下の整数を書き込み，以下の条件を満たしたいです．
- 左上のマスを出発し，右または下に隣接するマスへの移動を繰り返して，右下のマスへと至るパスを考える． ここで，通ったマス (始点終点を含む) に書かれた整数の総 \mathrm{XOR} が 0 になるパスを，よいパスと呼ぶことにする．
- よいパスはちょうど 1 つだけ存在し，それは文字列 S が表すパスである．
文字列 S が表すパスとは，各 i (1 \leq i \leq N+M-2) について，i 回目の移動の際，S の i 文字目が
Rなら右，Dなら下に進むようなパスである．
条件を満たす整数の書き込み方が存在するかどうか判定してください．
1 つの入力ファイルにつき，T 個のテストケースを解いてください．
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\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 個のRからなる文字列 - 入力される数はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
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
例えば 1 ケース目については，以下のようなグリッドを作れば良いです．
11 00
Score : 700 points
Problem Statement
We have a grid with N rows and M columns. You want to write an integer between 0 and 2^K-1 in each square in the grid to satisfy the following condition.
- Consider a path that starts at the top-left square, repeatedly moves right or down to an adjacent square, and ends at the bottom-right square. Such a path is said to be good if and only if the total \mathrm{XOR} of the integers written on the squares visited (including the starting and ending points) is 0.
- There is exactly one good path, which is the path represented by a string S.
The path represented by the string S is a path that, for each i (1 \leq i \leq N+M-2), the i-th move is right if the i-th character of S is
Rand down if that character isD.
Determine whether there is a way to write integers that satisfies the condition.
For each input file, solve T test cases.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows.
- When A \oplus B is written in binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq T \leq 100
- 2 \leq N,M \leq 30
- 1 \leq K \leq 30
- S is a string containing exactly N-1
Ds and M-1Rs. - All numbers in the input are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N M K S
Output
For each case, print Yes if there is a way to write integers that satisfies the condition, and No otherwise.
Each character in the output may be either uppercase or lowercase.
Sample Input 1
4 2 2 1 RD 4 3 1 RDDDR 15 20 18 DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR 20 15 7 DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD
Sample Output 1
Yes No Yes No
As an example, for the first case, you can make the grid as follows.
11 00