分数: 400 点
问题陈述
有一个 H\times W 单元格网格。让 (h,w) 表示位于 h从顶部算起的第行和 w左起第 列。此外,你还得到了一个字符串 S = S_1\cdots S_{H+W-2} 长度 H+W-2 组成 D, R,和 ?.
最初,所有单元格都漆成白色。您可以执行任意次数的以下操作,该操作由三个步骤组成:
- 选择一个字符串 X = X_1\cdots X_{H+W-2} 长度 H+W-2 满足以下所有条件。
- X 完全由 H-1
D和 W-1Rs。 - 对于每个 1 \le i \le H+W-2,如果 S_i is
D然后 X_i 还必须是D. - 对于每个 1 \le i \le H+W-2,如果 S_i is
R然后 X_i 还必须是R.
- X 完全由 H-1
- 站在电池上 (1,1)。那么对于 i=1,2,\ldots 按顺序,按 所示方向移动一个单元格 X_i:如果 X_i is
D,下移一个单元格;如果 X_i isR,右移一个单元格。可以证明如果 X 满足步骤1中的条件,目标单元格始终存在于网格内。 - 对于您在步骤 2 中访问的每个单元格(包括起始单元格和结束单元格),如果该单元格当前为白色,请将其涂成黑色。
找出总共可以涂成黑色的最大可能单元格数。
有 T 测试用例;逐一解决。
约束
- 1\le T\le 2\times 10^5
- 2\le H,W\le 2\times 10^5
- T,H,W 是整数。
- S 是一个长度为的字符串 H+W-2 组成
D,R,和?. - 数量
D位于 S 最多是 H-1. - 数量
R位于 S 最多是 W-1. - 总和 H+W 所有测试用例最多 4\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个案例均按以下格式给出:
H W S
输出
打印 T 行。的 i第行应包含可以涂黑的最大单元格数 i- 第一个测试用例。
示例输入 1
4 4 5 D?DRR?R 4 5 DDRRDRR 4 5 ??????? 2 2 DR
示例输出 1
12 8 20 3
对于第一个测试用例,通过选择 X as DRDRRDR 在第一次操作中并且 DDDRRRR 在第二次操作中,可以绘画 12 细胞黑色。
