Christmas Color Grid 1

题目描述

这个问题的设定与问题 G 相似。问题陈述中的差异以红色标注。 有一个高为 $H$、宽为 $W$ 的网格，每个格子被涂成红色或绿色。 令 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。 格子 $(i,j)$ 的颜色由字符 $S_{i,j}$ 表示，其中 $S_{i,j} =$ $.$ 表示格子 $(i,j)$ 为红色，$S_{i,j} =$ # 表示格子 $(i,j)$ 为绿色。 网格中绿色连通分量的个数是以绿色格子为点、并且连接两个相邻绿色格子的边为边的图的连通分量数。这里，当 $|x-x'| + |y-y'| = 1$ 时，认为格子 $(x,y)$ 和 $(x',y')$ 是相邻的。 考虑等概率地选择一个红色格子并将其重新涂成绿色。输出重新涂色后网格中绿色连通分量个数的期望值，结果对 $998244353$ 取模。

输入格式

输入按标准输入给出，格式如下： $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}$

输出格式

输出答案。

3 3
##.
#.#
#..

499122178

4 5
..#..
.###.
#####
..#..

598946613

3 4
#...
.#.#
..##

285212675

提示

$1 \leq H,W \leq 1000$ $S_{i,j} =$ $.$ 或 $S_{i,j} =$ #。 至少存在一个 $(i,j)$ 使得 $S_{i,j} =$ $.$。如果将格子 $(1,3)$ 重新涂成绿色，绿色连通分量的个数变为 $1$。 如果将格子 $(2,2)$ 重新涂成绿色，绿色连通分量的个数变为 $1$。 如果将格子 $(3,2)$ 重新涂成绿色，绿色连通分量的个数变为 $2$。 如果将格子 $(3,3)$ 重新涂成绿色，绿色连通分量的个数变为 $2$。 因此，等概率选择一个红色格子并将其重新涂成绿色后，绿色连通分量个数的期望值为 $(1+1+2+2)/4 = 3/2$。

标签: AtCoder|abc334E

来源

AtCoder|abc334E