← 返回题目列表

AtCoder · arc197_a

A. 网格路径的并集

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

分数: 400 点

问题陈述

有一个 H\times W 单元格网格。让 (h,w) 表示位于 h从顶部算起的第行和 w左起第 列。此外,你还得到了一个字符串 S = S_1\cdots S_{H+W-2} 长度 H+W-2 组成 D, R,和 ?.

最初,所有单元格都漆成白色。您可以执行任意次数的以下操作,该操作由三个步骤组成:

  1. 选择一个字符串 X = X_1\cdots X_{H+W-2} 长度 H+W-2 满足以下所有条件。
    • X 完全由 H-1 D和 W-1 Rs。
    • 对于每个 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.
  2. 站在电池上 (1,1)。那么对于 i=1,2,\ldots 按顺序,按 所示方向移动一个单元格 X_i:如果 X_i is D,下移一个单元格;如果 X_i is R,右移一个单元格。可以证明如果 X 满足步骤1中的条件,目标单元格始终存在于网格内。
  3. 对于您在步骤 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 细胞黑色。