题目理解

我们有一个 $n \times m$ 的网格，初始时：

• 有 $c$ 个格子是蛐蛐（障碍）
• 其余格子是跳蚤（可通行）

跳蚤的连通性是四连通的（上下左右相邻算连通）。

目标：将一些跳蚤变成蛐蛐，使得剩下的跳蚤中至少有两个不连通。要求替换的跳蚤数量最少。

思路分析

这个问题本质上是：在一个巨大的网格图中，有一些障碍（蛐蛐），其余是自由格子（跳蚤）。我们要通过增加障碍来破坏整个跳蚤区域的连通性，使得至少有两个连通分量。

1. 特殊情况

• 如果跳蚤总数 $nm - c \le 1$，那么不可能有两个跳蚤不连通，输出 -1。
• 如果初始时跳蚤已经不连通（有多个连通分量），那么不需要替换任何跳蚤，输出 0。

2. 一般情况

如果初始时整个跳蚤区域是连通的，那么我们需要通过增加蛐蛐来切断它。

在网格图中，切断连通性通常与割点或最小割有关。这里我们将跳蚤变成蛐蛐（相当于删除节点）。

3. 关键观察

• 网格图是平面图。
• 在平面图中，要断开连通性，通常只需要很少的障碍。
• 实际上，答案只可能是 $0, 1, 2$ 或 -1。
  • $0$：初始就不连通。
  • $1$：存在一个割点，即把某个跳蚤变成蛐蛐后图就不连通了。
  • $2$：需要至少两个点才能切断。
  • -1：不可能。

为什么最大是 $2$？
因为网格图是四连通的平面图，根据平面图的性质，最小割点集大小不会很大。实际上，对于矩形网格，最小割点集大小最多为 $2$（例如切掉一个 $2\times 2$ 的环需要至少去掉两个点）。

4. 如何判断

由于 $n, m$ 很大（$10^9$），但 $c \le 10^5$，我们不能直接建整个网格。

我们需要利用稀疏障碍的特点：

1. 判断初始连通性
   所有自由格子（跳蚤）形成一个图，但自由格子太多，无法显式存储。
   我们可以通过 BFS/DFS 只考虑障碍周围的格子，因为障碍很少，自由格子形成的连通块如果很大，会延伸到边界，我们可以用“障碍+边界”来划分自由格子的连通块。

   我们只需要考虑障碍物周围 $5\times 5$ 的区域（因为割点只可能出现在障碍物附近），以及整个网格的边界。

2. 判断是否存在大小为 1 的割集
   即是否存在一个跳蚤，去掉它后图不连通。
   在网格图中，这样的点通常是“桥”点，但网格图是 2-连通的（除了特殊情况）。
   特殊情况是：网格非常窄（$n=1$ 或 $m=1$）时，可能形成链，这时割点可能存在。
   对于 $n \ge 2, m \ge 2$ 的网格，去掉一个点通常不会断开整个图，除非该点处于关键位置（例如障碍物包围的狭窄通道）。

   我们可以枚举每个跳蚤格子，检查它是否是割点，但跳蚤格子太多。
   可能的割点只出现在障碍物周围的邻域内，因为远离障碍物的内部点去掉后图仍然连通（网格图是 2-连通的）。

   所以只需检查障碍物周围 $3\times 3$ 区域内的自由格子。

3. 判断是否存在大小为 2 的割集
   如果不存在大小为 1 的割集，就检查是否存在两个点可以切断连通性。
   同样，这两个点也只可能出现在障碍物周围的局部区域。

5. 实现方法

我们可以这样设计：

1. 如果 $nm - c \le 1$，输出 -1。
2. 如果 $nm - c = 2$ 且这两个跳蚤相邻，那么输出 -1（因为无法让它们不连通，除非全删掉，但那样就没有两只跳蚤了）。
3. 将障碍物坐标存入哈希集。
4. 从某个自由格子开始 BFS，看能否访问到所有自由格子（通过障碍物周围的局部 BFS，利用坐标哈希判断访问过）。
   • 如果 BFS 访问的自由格子数 < 总自由格子数，说明初始不连通，输出 0。
5. 检查是否存在一个跳蚤是割点：
   • 只检查障碍物周围 $3\times 3$ 区域内的自由格子。
   • 对每个候选点，暂时标记为障碍，再 BFS 检查是否连通，如果不连通，则输出 1。
6. 否则输出 2。

6. 边界情况

• 网格 $1\times 1$，$c=0$：只有一只跳蚤，输出 -1。
• 网格 $1\times 2$，$c=0$：两只跳蚤相邻，无法让它们不连通，输出 -1。
• 网格 $1\times 3$，$c=0$：链状，中间是割点，输出 1。

总结

我们利用网格图的平面性质和障碍稀疏的特点，将问题规模缩小到只考虑障碍物周围的局部区域，从而在 $O(c)$ 或 $O(c \log c)$ 时间内解决问题。