分数: 400 点
问题陈述
我们有一个网格 H 行和 W 列。让 (i, j) 表示位于 i第行和 j第列。
你被给予 H 字符串 S_1, S_2, S_3, \dots, S_H 描述正方形,如下:
- 如果 j- 第一个字符 S_i is
R, (i, j) 被涂成红色; - 如果 j- 第一个字符 S_i is
B, (i, j) 被涂成蓝色; - 如果 j- 第一个字符 S_i is
., (i, j) 未上漆。
让 k 是未绘制方块的数量。其中 2^k 将每个方块涂成红色或蓝色的方法,有多少个满足以下条件?
- 从以下位置访问时访问的红色方块的数量 (1, 1) to (H, W) 反复向右或向下移动一格,包括 (1, 1) 和 (H, W)始终相同,无论采用何种路径。
由于计数可能很大,因此将其模数打印出来 998244353.
约束
- 2 \le H \le 500
- 2 \le W \le 500
- S_i 是一个长度为 W 组成
R,B,和..
输入
输入由标准输入按以下格式给出:
H W
S_1
S_2
S_3
\hspace{3pt} \vdots
S_H
输出
打印计数模数 998244353.
示例输入 1
2 2 B. .R
示例输出 1
2
有两种方法可以从 (1, 1) to (2, 2) 通过反复向右或向下移动,如下:
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2)
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2)
如果我们画 (1, 2) 和 (2, 1) 以不同的颜色,上述两条路径将包含不同数量的红色方块,违反了条件。
另一方面,如果我们画 (1, 2) 和 (2, 1) 颜色相同,两条路径将包含相同数量的红色方块,满足条件。
因此,有两种方法可以满足该条件。
示例输入 2
3 3 R.R BBR ...
示例输出 2
0
可能无法满足该条件。
示例输入 3
2 2 BB BB
示例输出 3
1
没有未绘制的方块,且当前格子满足条件,所以答案为 1.