对于这个问题，使用深搜（DFS） 的核心思路是：二分答案 + DFS 判定连通性。

由于 \(n \le 50\)，二分 \(\log\) 上界约 \(31\) 次，每次判定 \(O(n^2)\)，完全可行。

算法步骤

1. 读入 \(n\) 个点的坐标。
2. 二分答案 \(t\)：
   • 下界 \(l = 0\)，上界 \(r = 2\times 10^9\)（或直接取坐标最大值 \(\times 2\)）。
   • 对每个中间值 \(\text{mid}\)，判定时刻 \(\text{mid}\) 时所有点的扩散区域是否构成一个连通块。
3. 判定函数 check(mid)：
   • 计算任意两点曼哈顿距离 \(d = |x_i - x_j| + |y_i - y_j|\)。
   • 若 \(d \le 2\times \text{mid}\)，则两点在时刻 \(\text{mid}\) 时连通（它们的扩散区域有交集）。
   • 用邻接表或直接暴力建图，从点 \(0\) 开始 DFS：
     • 标记访问过的点。
     • DFS 递归访问所有与当前点连通的点。
   • 最后检查是否所有点都被访问：若是则 return true，否则 false。
4. 二分结束后输出 \(l\)（即满足条件的最小整时刻）。

为什么使用深搜？

• 深搜简单直观，适合小规模图（\(n\le 50\)）的连通性判定。
• 与并查集等价，但 DFS 代码更易写，且递归深度不超过 \(50\)，无栈溢出风险。
• 二分 + DFS 是这类“最小时间连通”问题的经典解法。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

int n;
long long x[55], y[55];
bool vis[55];

bool dfs(int u, long long t) {
    vis[u] = true;
    for (int v = 0; v < n; ++v) {
        if (vis[v]) continue;
        long long d = abs(x[u] - x[v]) + abs(y[u] - y[v]);
        if (d <= 2 * t) dfs(v, t);
    }
    return true;
}

bool check(long long t) {
    memset(vis, 0, sizeof(vis));
    dfs(0, t);
    for (int i = 0; i < n; ++i)
        if (!vis[i]) return false;
    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    long long l = 0, r = 2e9;
    while (l < r) {
        long long mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

复杂度

• 二分次数 \(\approx \log_2(2\times 10^9) \le 31\)。
• 每次 check 遍历所有点对 \(O(n^2)\)，DFS 访问边 \(O(n^2)\)。
• 总复杂度 \(O(n^2 \log C)\)，\(n\le 50\) 时极快。

关键点提醒

• 曼哈顿距离是本题距离度量，欧氏距离不适用。
• 两圆盘相交条件为 曼哈顿距离 ≤ 2t，可直接推导。
• 答案一定是整数，且二分边界要足够大（坐标可达 \(10^9\)，扩散到连通可能需要接近 \(2\times 10^9\)）。

使用深搜做判定，代码简洁且正确。如果 \(n\) 更大（如 \(10^5\)），则需要改用并查集 + 排序优化，但本题 \(n\le 50\)，深搜完全足够。