AT_keyence2021_c.Robot on Grid

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 $H$ 行 $W$ 列的网格。我们将从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(i, j)$ 。每个格子都可以填写 R、D、X 这三种字符之一。初始时，所有格子都没有被填写任何字符。

すぬけ君选择了 $K$ 个格子并填写了字符。第 $i$ 个被填写的格子是 $(h_i, w_i)$ ，填写的字符是 $c_i$ 。

对于剩下的格子，有 $3^{HW-K}$ 种填写方式。对于每一种填写方式，请计算下述问题的答案，并将所有答案的总和对 $998244353$ 取模后输出。

有一个可以在上述网格上移动的机器人。机器人在 $(i, j)$ 时，可以移动到 $(i+1, j)$ 或 $(i, j+1)$ 。但如果 $(i, j)$ 被填写为 R，则只能移动到 $(i, j+1)$ ；如果被填写为 D，则只能移动到 $(i+1, j)$ ；如果被填写为 X，则两种移动都可以。

机器人初始放在 $(1, 1)$ ，请问机器人在不出界的情况下到达 $(H, W)$ 的路径有多少种？机器人到达 $(H, W)$ 后即停止。

这里，若两条路径经过的格子集合不同，则认为这两条路径不同。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$ $K$
$h_1$ $w_1$ $c_1$
$\vdots$
$h_K$ $w_K$ $c_K$

输出格式

请输出答案。

输入输出样例

输入#1
```
2 2 3
1 1 X
2 1 R
2 2 R
```
输出#1
```
5
```
输入#2
```
3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R
```
输出#2
```
150
```

输入#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

输出#3

139923295

说明/提示

限制条件

$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$
若 $i \neq j$ ，则 $(h_i, w_i) \neq (h_j, w_j)$
$c_i$ 是 R、D、X 中的一个

样例解释 1

只有 $(1,2)$ 还未被填写字符。
如果填写 R，机器人到达 $(H, W)$ 的路径有 $1$ 条。
如果填写 D，机器人到达 $(H, W)$ 的路径有 $2$ 条。
如果填写 X，机器人到达 $(H, W)$ 的路径有 $2$ 条。
这三种情况的总和为 $5$ ，请输出 $5$ 。

样例解释 3

不要忘记对 $998244353$ 取模。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页