水上公园 题解

问题分析

我们有一个 $n \times n$ 的网格，每个格子是 A（通道）或 B（泳池）。初始时所有泳池都是矩形连通块。我们可以将最多 2 个 A 格子改为 B，目标是最大化最大连通泳池的大小。

关键观察

1. 初始状态：所有泳池都是矩形，这意味着它们内部是连通的
2. 改造限制：最多改变 2 个 A 格子
3. 连通性：改造后泳池可以是非矩形的，但必须通过边相邻连接

算法思路

方法一：连通分量分析 + 枚举（小数据）

对于 $n \leq 60$：

1. 标记连通分量：

   • 使用 BFS/DFS 找到所有初始的泳池连通分量
   • 记录每个分量的 ID 和大小

2. 分析相邻关系：

   • 对于每个 A 格子，检查它连接了哪些泳池分量
   • 如果将一个 A 改为 B，可能连接多个分量

3. 枚举所有可能：

   • 枚举选择 0、1 或 2 个 A 格子进行改造
   • 对于每种选择，计算合并后的连通分量大小

方法二：优化枚举（大数据）

对于 $n \leq 1000$，需要更高效的算法：

1. 预处理分量信息：

   • 为每个分量分配唯一 ID
   • 记录每个分量的边界 A 格子

2. 分析关键连接点：

   • 只考虑那些连接多个分量的 A 格子
   • 维护每个 A 格子相邻的分量集合

3. 分类讨论：

   • 情况1：不改任何 A，最大分量就是答案
   • 情况2：改 1 个 A，连接多个分量
   • 情况3：改 2 个 A，可能连接更多分量

复杂度分析

• 连通分量分析：$O(n^2)$
• A格子分析：$O(n^2)$
• 枚举两个A：最坏 $O(n^4)$，但实际A格子数量有限

优化策略

对于大数据 ($n \leq 1000$)：

1. 限制A格子考虑：只考虑与泳池相邻的A格子
2. 分组处理：按连接的泳池分量对A格子分组
3. 避免重复计算：使用并查集或其它数据结构

样例验证

样例输入

5
BBBAB
BBBAB
AAAAA
BBABA
BBAAB

输出：14

分析：通过将某些A改为B，可以连接多个矩形泳池形成更大的连通区域。

特殊情况处理

• 全B情况：最大泳池就是整个网格
• 全A情况：最多只能有2个泳池格子
• 1x1泳池：子任务4的特殊情况

总结

本题需要结合连通分量分析和枚举优化技术。关键在于理解如何通过有限的改造最大化连通区域，并设计高效的算法来处理大规模网格。

最终算法标签： 连通分量 BFS/DFS 枚举优化 网格处理 图论