题意

$H\times W$ 的网格，有 $P$ 个建筑物和若干原野、墙壁。从建筑物 $S$ 走到 $T$，每经过一个原野需要 $1$ 升水，水壶可在建筑物装满。求 $Q$ 个询问中，从 $S$ 到 $T$ 所需的最小水壶容量。

题解1

思路

题目后半部分是经典的 Kruskal重构树 类问题（瓶颈树），也就是求图上两点之间所有路径中最大值最小的。

所以基本思路是建立 Kruskal重构树后，对于每次询问找到点 $u,v$ 在树上的 LCA 。

复杂度瓶颈在与如何求最小生成树。

如果使用最暴力的 BFS ,求出任意两点之间的距离，复杂度为 $O(w*h*p)$ ,只能通过最小的测试数据点，同时由于边的数量为 $p^2$ ,也很难通过后续测试点。

考虑多源BFS，对地图上每个点求出最近的两个不同城市 $(x,y)$ ，显然对于某个点 $(i,j)$ 来说,经过他的最近的一条链接两个城市为 $(x,y)$ 。

此时对于每一个点，都可以找到一条边，边的总数为 $w*h$。在可以接受的复杂度范围内。

为什么一定能求出最小生成树？

因为首先对于每个城市，自己到当前点的最近距离为$0$ ，所以对于每个点一定都存在一条边，由于平面图性质，任意所有边一定能形成一个连通块。

代码略。

---

题解2：

算法思路

问题转化

对于一条从 $S$ 到 $T$ 的路径，它由若干段组成，每段都是从某个建筑物出发，途经若干原野，到达另一个建筑物（或终点）。
因为水壶只在建筑物处才能装满，所以一次连续行走能经过的原野数上限就是水壶容量。
因此，最小所需水壶容量 就是所有可行路径中，“连续经过原野的最大长度”的最小值。

这本质上是一个最小瓶颈路问题：
把每个建筑物看作图上的结点，任意两个建筑物之间若存在一条只经过原野的路径，则这条路径的“代价”定义为该路径上连续原野的最大长度。
我们需要求任意两个建筑物之间的最小瓶颈路。

---

直接建图的困难

若对每个建筑物对都计算它们之间的瓶颈值，边数将达到 $O(P^2)$，不可接受。
我们需要利用网格的局部性，通过多源 BFS 来压缩边数。

---

多源 BFS 建图

步骤 1：多源 BFS
从所有 $P$ 个建筑物同时开始 BFS（遇到墙壁则停止），对每个格子 $u$ 记录：

• dist[u]：该格子到最近的建筑物的最短距离（即经过的原野数）；
• owner[u]：该最近建筑物的编号。

这样，每个格子都被“分配”给了离它最近的建筑物，形成了 $P$ 个 Voronoi 区域。

步骤 2：构造候选边
遍历所有相邻格子对（上下左右），设 $u, v$ 相邻。

• 如果 owner[u] != owner[v] 且两个格子都可通行，那么这是一条“跨越”了两个不同建筑物区域的边。
• 我们添加一条连接建筑物 owner[u] 和 owner[v] 的无向边，权值为 dist[u] + dist[v]。

为什么权值取 dist[u] + dist[v]？
因为从 owner[u] 到 $u$ 的最短距离是 dist[u]，从 owner[v] 到 $v$ 的最短距离是 dist[v]，而 $u,v$ 相邻，所以从 owner[u] 到 owner[v] 可以走： owner[u] -> ... -> u -> v -> ... -> owner[v]
这条路径上连续经过的原野数恰好为 dist[u] + dist[v]（假设 $u, v$ 本身是原野或建筑物，距离计算已包含）。

步骤 3：Kruskal 重构树
对上述得到的边集（边数 $\le 4HW$）按权值从小到大排序，跑 Kruskal 最小生成树，并同时构建 Kruskal 重构树。
在重构树中，每个叶子结点对应原始建筑物，每个内部结点代表合并两个连通块时的那条边，其权值为该边的权值。
则任意两个建筑物 $S, T$ 的最小瓶颈路答案就是它们在重构树中 LCA 的权值（若它们连通）。

---

正确性证明

引理 1：上述建图方法得到的图 $G'$（建筑物为点，边权为 dist[u]+dist[v]）与原始网格图 $G$ 具有相同的最小瓶颈路结构。

证明要点：

• （1）每条 $G'$ 中的边都对应 $G$ 中的一条路径，且瓶颈不超过该边权。
  对于边 $(A,B)$，它来自相邻格子 $u,v$ 且 $owner[u]=A, owner[v]=B$。
  从 $A$ 沿最短路走到 $u$（长度 dist[u]），过 $u\to v$，再沿最短路从 $v$ 到 $B$（长度 dist[v]），整条路径连续原野数最多为 dist[u]+dist[v]。因此该边在 $G$ 中可实现。

• （2）任意一条 $G$ 中的路径，都能映射为 $G'$ 中的一条路径，且 $G'$ 路径的最大边权不超过原路径的瓶颈。
  沿着原路径走，记录所有相邻格子对中 owner 发生变化的位置。每发生一次变化，例如从 $x$ 到 $y$（相邻且归属不同），则在 $G'$ 中存在边 $(owner[x], owner[y])$，权值为 dist[x]+dist[y]。
  原路径中从 $owner[x]$ 到 $x$ 的部分，其连续原野长度至少为 dist[x]（因为最短路长度是下界），同理从 $y$ 到 $owner[y]$ 至少为 dist[y]。
  因此原路径的瓶颈（最大连续原野长度）不小于 dist[x]+dist[y]，故映射后的 $G'$ 路径的每条边权都不超过原瓶颈。

• （3）由于任意 $G'$ 路径可嵌入 $G$，任意 $G$ 路径可映射为 $G'$ 路径且瓶颈不增，两者最小瓶颈路相等。
  因此，$G'$ 上任意两点间的最小瓶颈边权等于 $G$ 中两建筑物的最小水壶容量。

引理 2：$G'$ 的边数 $\le 4HW$。
因为只枚举相邻格子对，每个格子最多贡献 4 条候选边（上下左右），所以边数 $O(HW)$，远小于 $P^2$。

引理 3：Kruskal 重构树上的 LCA 权值即为最小瓶颈路值。
这是 Kruskal 重构树的标准性质，不再赘述。

---

复杂度分析

• 多源 BFS：$O(HW)$。
• 建边：遍历 $4HW$ 条相邻关系，$O(HW)$。
• 排序边：$O(HW \log(HW))$。
• Kruskal：$O(HW \cdot \alpha(P))$。
• 预处理 LCA（倍增）：$O(P\log P)$。
• 每个询问 $O(\log P)$。

总时间复杂度：$O(HW \log(HW) + Q \log P)$，空间 $O(HW+P\log P)$，可以轻松通过。

---

参考代码（C++）

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

int H, W, P, Q;
vector<string> grid;
vector<int> dist, owner;
vector<pair<int,int>> buildings;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
inline int id(int x, int y) { return x * W + y; }

void multiBFS() {
    dist.assign(H * W, -1);
    owner.assign(H * W, -1);
    queue<int> q;
    for (int i = 0; i < P; i++) {
        int u = id(buildings[i].first, buildings[i].second);
        dist[u] = 0; owner[u] = i; q.push(u);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        int x = u / W, y = u % W;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (grid[nx][ny] == '#') continue;
            int v = id(nx, ny);
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                owner[v] = owner[u];
                q.push(v);
            }
        }
    }
}

struct DSU {
    vector<int> fa;
    DSU(int n) : fa(n) { iota(fa.begin(), fa.end(), 0); }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> H >> W >> P >> Q;
    grid.resize(H);
    for (int i = 0; i < H; i++) cin >> grid[i];

    buildings.resize(P);
    for (int i = 0; i < P; i++) {
        cin >> buildings[i].first >> buildings[i].second;
        buildings[i].first--; buildings[i].second--;
    }

    multiBFS();

    // 构造边
    vector<array<int,3>> edges; // {w, u, v}
    for (int x = 0; x < H; x++) {
        for (int y = 0; y < W; y++) {
            int u = id(x, y);
            if (dist[u] == -1) continue;
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (grid[nx][ny] == '#') continue;
                int v = id(nx, ny);
                if (dist[v] == -1) continue;
                if (owner[u] != owner[v]) {
                    edges.push_back({dist[u] + dist[v], owner[u], owner[v]});
                }
            }
        }
    }

    sort(edges.begin(), edges.end());
    int tot = P;
    vector<int> val(2 * P, 0);
    vector<vector<int>> tree(2 * P);
    DSU dsu(2 * P);

    for (auto &e : edges) {
        int w = e[0], a = dsu.find(e[1]), b = dsu.find(e[2]);
        if (a == b) continue;
        int node = tot++;
        val[node] = w;
        tree[node].push_back(a);
        tree[node].push_back(b);
        dsu.fa[a] = dsu.fa[b] = node;
    }

    // 倍增 LCA 预处理
    int LOG = 20;
    vector<vector<int>> up(tot, vector<int>(LOG, -1));
    vector<int> depth(tot, 0);
    function<void(int,int)> dfs = [&](int u, int p) {
        up[u][0] = p;
        for (int k = 1; k < LOG; k++) {
            if (up[u][k-1] != -1)
                up[u][k] = up[up[u][k-1]][k-1];
        }
        for (int v : tree[u]) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    };
    for (int i = 0; i < tot; i++) {
        if (dsu.find(i) == i && !tree[i].empty()) {
            dfs(i, -1);
        }
    }

    auto lca = [&](int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        for (int k = LOG-1; k >= 0; k--) {
            if (up[a][k] != -1 && depth[up[a][k]] >= depth[b])
                a = up[a][k];
        }
        if (a == b) return a;
        for (int k = LOG-1; k >= 0; k--) {
            if (up[a][k] != -1 && up[a][k] != up[b][k]) {
                a = up[a][k];
                b = up[b][k];
            }
        }
        return up[a][0];
    };

    while (Q--) {
        int S, T;
        cin >> S >> T; S--; T--;
        if (S == T) { cout << 0 << '\n'; continue; }
        if (dsu.find(S) != dsu.find(T)) { cout << -1 << '\n'; continue; }
        cout << val[lca(S, T)] << '\n';
    }

    return 0;
}