H1. 最大化最大连通分量（简单版）详细题解

题目重述

给定一个 $n \times m$ 的网格，由 '.'（空）和 '#'（障碍）组成。一次操作可以选择任意一行或任意一列，将该行或该列的所有格子变成 '#'。要求执行至多一次操作后，整个网格中最大的 '#' 连通分量（四连通）的大小。输出这个最大可能大小。

核心思路

• 如果不进行操作，答案就是原图中最大的 '#' 连通分量的大小。
• 如果进行操作，我们有两种选择：选择某一行，或者选择某一列。由于操作将整行或整列变为 '#'，这相当于在网格中添加了许多新的 '#'，它们可能将原本分离的多个分量连接起来，形成一个更大的分量。
• 我们需要分别考虑每一行和每一列，计算出将该行/列全变为 '#' 后，能得到的最大连通分量大小，并取全局最大值。

预处理：连通分量标记

首先，对初始网格中的所有 '#' 进行 Flood Fill（BFS/DFS），标记每个 '#' 所属的连通分量编号，并记录每个分量的大小 $size[comp]$。同时，我们也可以记录每个格子是否属于某个分量（非 '#' 的格子暂时不属于任何分量）。

计算操作一行的影响

假设我们选择第 $r$ 行（$0$-based），将该行的所有 $m$ 个格子全部变为 '#'。这会产生一个“新行”，它由 $m$ 个 '#' 组成。这些新格子可能连接以下三种来源的 '#'：

1. 该行中原有的 '#'（它们原本属于某些分量）。
2. 该行上下相邻的行中的 '#'，因为新行的每个格子会与上、下邻接的格子连通。
3. 该行本身的连续格子之间互相连通，因此整个新行内部自动连通成一个整体。

实际上，新行会连接所有与它相邻（上、下）的 '#' 分量，以及该行中原有的 '#' 分量。这些分量通过新行融合成一个大的连通分量。此外，新行中原本为 '.' 的格子现在变成了 '#'，它们也会连接左右邻居，但左右邻居已经包含在整行的连通性中。

因此，为了计算操作后包含该行的最大分量的大小，我们需要考虑：

• 新行本身贡献 $m$ 个格子。
• 所有与新行相邻的不同分量（包括该行中原有的分量以及上下行中的分量），每个分量会贡献其全部大小，但需要减去该分量中位于新行上的格子数，因为这些格子在新行中已经被计入了 $m$（否则会重复计算）。

更精确地：设 $S$ 为所有满足“该分量的某个格子与新行相邻（包括位于新行本身、位于上一行或下一行）”的不同分量的集合。对于每个分量 $c$，设 $cnt_{row}(c)$ 表示该分量位于第 $r$ 行的格子数（注意，如果分量存在于上行或下行，它们不在本行，所以 $cnt_{row}(c)$ 可能为 $0$）。则操作后包含新行的最大连通分量的大小为：

$$total = m + \sum_{c \in S} \big( size[c] - cnt_{row}(c) \big). $$

因为新行已经提供了 $m$ 个格子，而每个分量中除了已经被新行包含的格子外，其余格子都会通过新行连接到一起。注意，不同分量之间原本不连通，但新行将它们全部连接起来了，所以最终形成一个大的分量。

实现时，我们可以：

• 对于当前行 $r$，用一个集合（或哈希表）记录所有“接触”到的分量。
  • 首先，遍历该行每个格子，如果格子是 '#'，则将其分量编号加入集合，并记录该分量在本行的出现次数（可以用一个哈希表 cnt）。
  • 然后，遍历该行每个格子，检查上、下邻居（如果存在且为 '#'），将其分量编号也加入集合（计数为 $0$，因为不在本行）。
• 然后计算 $total = m + \sum_{c \in S} (size[c] - cnt[c])$。
• 用 $total$ 更新答案。

计算操作一列的影响

类似地，选择第 $c$ 列，将该列全部变为 '#'，得到 $n$ 个新格子。它们会连接左右相邻列以及该列原有的 '#' 分量。设 $S$ 为所有与当前列相邻（包括本列、左列、右列）的不同分量的集合，$cnt_{col}(c)$ 表示分量 $c$ 位于当前列的格子数。则操作后包含该列的最大分量大小为：

$$total = n + \sum_{c \in S} \big( size[c] - cnt_{col}(c) \big). $$

同样地，遍历该列每个格子及其左、右邻居，收集分量，并计算即可。

最终答案

• 答案初始值为原图最大连通分量大小（不进行任何操作）。
• 遍历所有行，按上述方法计算操作该行后的最大可能值，更新答案。
• 遍历所有列，按上述方法计算操作该列后的最大可能值，更新答案。
• 输出答案。

正确性说明

• 操作一行后，所有新加入的 $m$ 个格子自身形成一个连通块（因为整行连续），并且它们会与上、下行的 '#' 以及本行原有的 '#' 连通。因此，所有与新行接触的分量都会通过新行合并为一个连通分量。该分量的总大小就是新行的格子数加上各分量中不在新行上的格子数。
• 上述计算方式恰好避免了重复计数（因为每个分量中位于本行的格子已经算在了 $m$ 中，只需要加上分量中剩余的部分）。
• 对于列的分析完全对称。
• 由于我们枚举了所有可能的行和列，并且考虑了不操作的情况，因此一定能得到最优值。

复杂度分析

• 预处理连通分量：$O(n \cdot m)$，BFS/DFS 每个格子访问一次。
• 对于每一行：需要遍历该行的 $m$ 个格子，并检查上下行，每个格子最多带来常数次哈希表操作。总复杂度 $O(n \cdot m)$。
• 对于每一列：类似 $O(n \cdot m)$。
• 总复杂度 $O(n \cdot m)$，由于所有测试用例的 $n \cdot m$ 之和不超过 $10^6$，完全可行。

边界情况

• 若原图没有 '#'，则原图最大分量为 $0$。此时操作一行会得到 $m$ 个 '#'，它们自身连通，大小为 $m$；操作一列同理。答案应为 $\max(m, n, 0)$，但注意 $n,m \ge 1$，实际上输出 $\max(n, m)$。
• 若原图已有大分量，操作后可能不会更大，答案取原值即可。

示例验证

以第二个测试用例为例：

4 2
..
#.
#.
.#

原图 '#' 位置：(1,0), (2,0), (3,1)。三个分量（互相不连通），大小均为 1。操作第2列（下标1）：

• 该列有原 '#' 在 (3,1)，所以接触的分量包括：该分量（cnt=1），以及左邻列 (1,0) 和 (2,0) 的分量（因为左邻列有 '#'）。故 S 包含三个分量，每个 size=1，cnt 分别为 1,0,0。计算 total = n + (1-1)+(1-0)+(1-0) = 4 + 0+1+1 = 6，正确。

总结

本题的关键在于将操作后连通分量大小的计算转化为：新行/列的格子数 + 所有相邻分量中不在该行/列上的格子数之和。通过预处理连通分量，然后枚举每一行和每一列，使用哈希集合去重即可高效求解。这种方法避免了模拟整个操作后的图，复杂度线性，适合 $n \cdot m \le 10^6$ 的数据范围。