Union of Grid Paths

AtCoder

IDarc197_a

Time2000ms

Memory256MB

Difficulty—

There is an $H\times W$ grid of cells. Let $(h,w)$ denote the cell at the $h$\-th row from the top and the $w$\-th column from the left. Furthermore, you are given a string $S = S_1\cdots S_{H+W-2}$ of length $H+W-2$ consisting of `D`, `R`, and `?`. Initially, all cells are painted white. You may perform the following operation, which consists of three steps, any number of times: 1. Choose a string $X = X_1\cdots X_{H+W-2}$ of length $H+W-2$ satisfying all of the following. * $X$ consists of exactly $H-1$ `D`s and $W-1$ `R`s. * For each $1 \le i \le H+W-2$, if $S_i$ is `D` then $X_i$ must also be `D`. * For each $1 \le i \le H+W-2$, if $S_i$ is `R` then $X_i$ must also be `R`. 2. Stand on cell $(1,1)$. Then for $i=1,2,\ldots$ in order, move one cell in the direction indicated by $X_i$: if $X_i$ is `D`, move down one cell; if $X_i$ is `R`, move right one cell. It can be shown that if $X$ satisfies the conditions in step 1, the destination cell always exists within the grid. 3. For every cell you visited in step 2 (including the starting and ending cells), if the cell is currently white, paint it black. Find the maximum possible number of cells that can be painted black in total. There are $T$ test cases; solve each one. ## Constraints * $1\le T\le 2\times 10^5$ * $2\le H,W\le 2\times 10^5$ * $T,H,W$ are integers. * $S$ is a string of length $H+W-2$ consisting of `D`, `R`, and `?`. * The number of `D`s in $S$ is at most $H-1$. * The number of `R`s in $S$ is at most $W-1$. * The sum of $H+W$ over all test cases is at most $4\times 10^5$. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\vdots$ $\text{case}_T$ Each case is given in the following format: $H$ $W$ $S$ [samples]

Samples

Input #1

4
4 5
D?DRR?R
4 5
DDRRDRR
4 5
???????
2 2
DR

Output #1

12
8
20
3

For the first test case, by choosing $X$ as `DRDRRDR` in the first operation and `DDDRRRR` in the second operation, you can paint $12$ cells black.
![image](https://img.atcoder.jp/arc197/fe14a42d236585f23bf6e59480bb45ac.png)

API Response (JSON)

{
  "problem": {
    "name": "Union of Grid Paths",
    "description": {
      "content": "There is an $H\\times W$ grid of cells. Let $(h,w)$ denote the cell at the $h$\\-th row from the top and the $w$\\-th column from the left. Furthermore, you are given a string $S = S_1\\cdots S_{H+W-2}$ o",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc197_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is an $H\\times W$ grid of cells. Let $(h,w)$ denote the cell at the $h$\\-th row from the top and the $w$\\-th column from the left. Furthermore, you are given a string $S = S_1\\cdots S_{H+W-2}$ o...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments