← 返回题目列表

AtCoder · keyence2021_c

C. 网格上的机器人

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

分数: 500 点

问题陈述

我们有一个网格 H 行和 W 方格列。 (i, j) 表示 i从顶部开始的第行和 j左起第 列。 在每个方格上,我们可以写一个字母: R, D,或 X。最初,每个方块都是空的。

Snuke 选择了 K 的方块并在上面写下字符。 的 i他选择的第一个方格是 (h_i,w_i),他写了这封信 c_i 就可以了。

有 3^{HW-K} 在剩下的每个方格上写一个字母的方法。求下列问题所有答案的总和 3^{HW-K} 方式,模数 998244353.

我们有一个可以在网格上行走的机器人。 当它在 (i,j),可以移动到 (i+1, j) or (i, j+1).
但是,如果 R 写在 (i, j),只能移动到 (i, j+1);如果 D 写在 (i, j),只能移动到 (i+1, j)。如果 X 写在 (i, j),两种选择都是可能的。

当机器人置于 (1, 1),机器人可以走多少条路径到达 (H, W) 不脱离电网?我们假设机器人在到达时停止 (H, W).

在这里,当机器人走过的方格组不同时,我们区分两条路径。

约束

  • 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) 为 i \neq j.
  • c_i is R, D,或 X.

输入

输入由标准输入按以下格式给出:

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
  • 仅 (1,2) 为空。
    • 如果我们写 R 上面,机器人可以采取一种方式到达 (H, W).
    • 如果我们写 D 上面,机器人可以采取两种方式到达 (H, W).
    • 如果我们写 X 上面,机器人可以采取两种方式到达 (H, W).
  • 我们应该打印这些计数的总和: 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
  • 请务必计算总和模 998244353.