Robot on Grid

AtCoder

IDkeyence2021_c

Time3000ms

Memory256MB

Difficulty—

We have a grid with $H$ rows and $W$ columns of squares. Let $(i, j)$ denote the square at the $i$\-th row from the top and $j$\-th column from the left. On each square, we can write a letter: `R`, `D`, or `X`. Initially, every square is empty. Snuke chose $K$ of the squares and wrote characters on them. The $i$\-th square he chose was $(h_i,w_i)$, and he wrote the letter $c_i$ on it. There are $3^{HW-K}$ ways to write a letter on each of the remaining squares. Find the sum of the answers to the problem below for all those $3^{HW-K}$ ways, modulo $998244353$. > We have a robot that can walk on the grid. When it is at $(i,j)$, it can move to $(i+1, j)$ or $(i, j+1)$. > However, if `R` is written on $(i, j)$, it can only move to $(i, j+1)$; if `D` is written on $(i, j)$, it can only move to $(i+1, j)$. If `X` is written on $(i, j)$, both choices are possible. > When the robot is put at $(1, 1)$, how many paths can the robot take to reach $(H, W)$ without going out of the grid? We assume the robot halts when reaching $(H, W)$. > Here, we distinguish two paths when the sets of squares traversed by the robot are different. ## Constraints * $2 \leq H,W \leq 5000$ * $0 \leq K \leq \min(HW,2 \times 10^5)$ * $1 \leq h_i \leq H$ * $1 \leq w_i \leq W$ * $(h_i,w_i) \neq (h_j,w_j)$ for $i \neq j$. * $c_i$ is `R`, `D`, or `X`. ## Input Input is given from Standard Input in the following format: $H$ $W$ $K$ $h_1$ $w_1$ $c_1$ $\vdots$ $h_K$ $w_K$ $c_K$ [samples]

Samples

Input #1

Output #1

5

*   Only $(1,2)$ is empty.
    *   If we write `R` on it, there is one way that the robot can take to reach $(H, W)$.
    *   If we write `D` on it, there are two ways that the robot can take to reach $(H, W)$.
    *   If we write `X` on it, there are two ways that the robot can take to reach $(H, W)$.
*   We should print the sum of these counts: $5$.

Input #2

Output #2

Input #3

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

Output #3

139923295

*   Be sure to compute the sum modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Robot on Grid",
    "description": {
      "content": "We have a grid with $H$ rows and $W$ columns of squares. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. On each square, we can write a letter: `R`, `D",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "keyence2021_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a grid with $H$ rows and $W$ columns of squares. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. On each square, we can write a letter: `R`, `D...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments