AT_abc334_e [ABC334E] Christmas Color Grid 1

[problemUrl]: https://atcoder.jp/contests/abc334/tasks/abc334_e **本题与问题 G 的设定相似。与问题 G 的不同之处已用红字标出。** 有一个 $H$ 行 $W$ 列的网格，每个格子被涂成红色或绿色。 网格中从上到下第 $i$ 行，从左到右第 $j$ 列的格子记作格子 $(i,j)$。 格子 $(i,j)$ 的颜色用字符 $S_{i,j}$ 表示，若 $S_{i,j} = . $，则格子 $(i,j)$ 被涂成红色；若 $S_{i,j} = \#$，则格子 $(i,j)$ 被涂成绿色。 在网格中，以所有被涂成绿色的格子为顶点集合，所有相邻的两个绿色格子之间连一条边，构成一个图。该图的连通分量个数称为**绿色连通分量数**。这里，两个格子 $(x,y)$ 和 $(x',y')$ 相邻，指的是 $|x-x'| + |y-y'| = 1$。 从所有被涂成**红色**的格子中等概率随机选择一个，将其涂成**绿色**后，输出涂色后的网格中绿色连通分量数的期望值，结果对 $998244353$ 取模。 “对 $998244353$ 取模输出期望值”是指，所求期望值一定是有理数。在本题的约束下，可以证明存在互质的两个整数 $P$、$Q$，使得期望值为 $\frac{P}{Q}$，并且存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入按以下格式从标准输入读入。 > $H$ $W$ > $S_{1,1} S_{1,2} \ldots S_{1,W}$ > $S_{2,1} S_{2,2} \ldots S_{2,W}$ > $\vdots$ > $S_{H,1} S_{H,2} \ldots S_{H,W}$

请输出答案。

### 约束 - $1 \leq H, W \leq 1000$ - $S_{i,j} = .$ 或 $S_{i,j} = \#$ - 存在至少一个 $(i,j)$ 使得 $S_{i,j} = .$ ### 样例解释 1 将格子 $(1,3)$ 涂成绿色后，绿色连通分量数为 $1$。 将格子 $(2,2)$ 涂成绿色后，绿色连通分量数为 $1$。 将格子 $(3,2)$ 涂成绿色后，绿色连通分量数为 $2$。 将格子 $(3,3)$ 涂成绿色后，绿色连通分量数为 $2$。 因此，等概率随机选择一个红色格子并涂成绿色后，绿色连通分量数的期望值为 $(1+1+2+2)/4 = 3/2$。 由 ChatGPT 4.1 翻译