CF1985H1

· · 题解

题意

给定一个由 # 和 . 组成的 n \times m 的网格，请进行以下的操作一次，使图中由 # 构成的连通块最大。

操作：选定一行或一列，将其全部变为 #。

输出操作后最大连通块点数。

思路

很自然地想到枚举每一行/每一列，难点在于怎么计算答案。

我们先考虑填行的情况。

如果我们把一行填满，则相当于桥一样把这条线两边的连通块连起来了。

所以当我们枚举第 i 行时，答案为：第 i 行 . 的数量，并将第 i - 1 到 i + 1 这三行的连通块不重不漏地加入贡献。

这里选择先 \text{dfs} 给每个连通块标个号，并计算该连通块大小。时间复杂度 O(nm)。

然后计算答案的时候，用 \text{map} 对编号去一下重，就能做到不重了。

填列的做法和填行没有任何区别。

代码

代码复杂程度远难于思路的一题。

Link.