IOI 市是一个被分成 r 行，c 列的矩形，每个小矩形都是建筑物、原野、墙壁之一。建筑物的区域有 n 个，编号为 1, 2, ..., n。
scx 只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。
由于 scx 要做各种各样的事情，必须在各个建筑物之间往返。可是原野上的日光十分强烈，每走过一格原野都需要 1 单位的水。
又原野上没有诸如自动售货机、饮水处之类的东西，因此 IOI 市的市民一般都携带水壶出行。大小为 x 的水壶最多可以装 x 单位的水，所有建筑物里都有水可以将水壶装满。
由于携带大水壶是一件很困难的事情，因此 scx 决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮她写一个程序来计算最少需要多大的水壶。
现在给出 IOI 市的地图和 q 个询问，第 i个询问为 "在建筑物 Si 和 Ti 之间移动，至少需要多大的水壶？"，请你对于每个询问输出对应的答案。
第一行包含四个整数 r, c, n, q，意义如描述所述。
接下来 r 行，每行有一个长度为 c 的字符串，每个字符都是 . 或 # 之一，.表示这个位置是建筑物或原野，#表示这个位置是和墙壁。
接下来 n 行描述 IOI 市每个建筑物的位置，第 i 行有两个整数 Ai 和 Bi，表示第 i 个建筑物的位置在第 Ai 行第 Bi 列。保证这个位置在地图中是 .。
接下来 q 行，第 i 行有两个空格分隔的整数 Si 和 Ti ，表示第 i 个询问为 "在建筑物 Si 和 Ti 之间移动，至少需要多大的水壶？"
输出 q 行，第 i 行的整数表示在建筑物 Si 和 Ti 之间移动至少需要多大的水壶。如果无法到达，输出 -1。此外，如果不需要经过原野就能到达，输出 0。
可以比较显然滴发现，可以将 n 个建筑物看成 n 个节点，点 Si 和点 Ti 的答案就是最小生成树中 Si 到 Ti 的路径中最大边的权值。
然后就是建立 Minimum Spanning Tree 了。
而原图的节点数为 2 × 105，如果两两连边，则边数最大为 2 × 1010，那么即使是 ，所以需要探究图本身的性质。 的最小生成树算法估计都过不去
由于该图在一个平面上的，所以我们可以设法将它变成一个平面图后再跑生成树。那么我们可以采用 bfs，以每个建筑物 (节点) 为圆心按照 Manhattan 距离扩展，如果两个建筑物在扩展时碰到了，再连边，这样就得到了一个平面图。
(scx: 可是节点数有 2 × 105 啊！保证边数不会太大吗？)
不会的，平面图有一个定理：，证明可以在
任何一本涉及到平面图的书中找到。也就是说，在平面图中，边数和点数呈线性关系。
然后跑完 Kruskal (或 Prim 或其它) 后，就是两点路径的最大边。
然而这玩意儿，就可以用像 LCA 一样的 (其实就是 LCA 模板改一改) 倍增算法在单次询问 时间内算出来。
(听说有一种高端的长链剖分可以做到单次询问 )
不过要注意的是，由于墙壁可能非常多导致某两个建筑物之间无法到达 (scx 一定很着急)，因此需要最后询问的时候，如果两个点不在同一个可到达集合中，就直接输出 -1 啦 (所以还是推荐写 Kruskal 吧，顺便就把并查集建出来了)。
#include <bits/stdc++.h>
#define S 2034
#define S2 4012249
#define maxV 256101
#define maxE 4012249
#define ID(x) id[x.r][x.c]
#define F(x) f[x.r][x.c]
using namespace std;
struct pr{
int r, c;
pr (int r0 = 0, int c0 = 0): r(r0), c(c0) {}
pr *scan(){scanf("%d%d", &r, &c); return this;}
};
struct edge{
int u, v, w;
edge (int u0 = 0, int v0 = 0, int w0 = 0): u(u0), v(v0), w(w0) {}
bool operator < (const edge &b) const {return w < b.w;}
};
struct UFind{
int sz, *p;
UFind (): sz(0) {p = NULL;}
~UFind () {if(p) delete [] (p);}
void resize(int size){
if(p) delete [] (p); p = new int[(sz = size) + 1];
for(int i = 0; i <= sz; i++) p[i] = i;
}
int ancestor(int x){return x == p[x] ? x : p[x] = ancestor(p[x]);}
bool test(int x, int y, bool un = false){
if((x = ancestor(x)) == (y = ancestor(y))) return false;
if(un) p[x] = y; return true;
}
};
const int dr[4] = {0, -1, 0, 1};
const int dc[4] = {-1, 0, 1, 0};
// E0: planar graph, Es: minimum spanning tree
int R, C, V, E0, Es;
int q, u, v, i;
// map[i][j]
char m[S][S];
// for bfs, id[i][j]: the owner of point (i, j), f[i][j]: distance from (i, j) to id[i][j]
int f[S][S], id[S][S];
pr a[maxV], que[S2];
// adjacent list
edge e0[maxE << 1], es[maxV << 1];
int first[maxV], next[maxV << 1];
// union find
UFind uf;
// for dfs
int dep[maxV], P[maxV][19], D[maxV][19];
inline void up(int &x, int y){x < y ? x = y : 0;}
inline void addedge0(int u, int v, int w){
if(e0[E0 - 1].u == u && e0[E0 - 1].v == v) return;
e0[++E0] = edge(u, v, w); e0[++E0] = edge(v, u, w);
}
inline void addedges(int u, int v, int w){
es[++Es] = edge(u, v, w); next[Es] = first[u]; first[u] = Es;
es[++Es] = edge(v, u, w); next[Es] = first[v]; first[v] = Es;
}
void bfs(){
int h, t, i;
pr z1, z2;
for(E0 = t = 0; t < V; t++){que[t] = a[t + 1]; ID(a[t + 1]) = t + 1;}
for(h = 0; h < t; h++)
for(z1 = que[h], i = 0; i < 4; i++){
if(m[z2.r = z1.r + dr[i]][z2.c = z1.c + dc[i]] != '.') continue;
if(!ID(z2)){
ID(z2) = ID(z1); F(z2) = F(z1) + 1;
que[t++] = z2;
}else if(ID(z1) < ID(z2))
addedge0(ID(z1), ID(z2), F(z1) + F(z2));
}
}
void Kruskal(){
uf.resize(V);
sort(e0 + 1, e0 + (E0 + 1));
for(Es = 0, i = 1; i <= E0; i++)
if(uf.test(e0[i].u, e0[i].v, true)){
addedges(e0[i].u, e0[i].v, e0[i].w);
if(Es >= V - 1 << 1) return;
}
}
void dfs(int x){
int i, y;
for(i = 0; i < 18 && P[x][i]; i++){
P[x][i + 1] = P[x][i][P][i];
D[x][i + 1] = max(D[x][i], P[x][i][D][i]);
}
for(i = first[x]; i; i = next[i])
if((y = es[i].v) != P[x][0]){
P[y][0] = x; D[y][0] = es[i].w;
dep[y] = dep[x] + 1; dfs(y);
}
}
int query(int x, int y){
if(uf.test(x, y)) return -1;
int res = 0;
if(dep[x] < dep[y]) swap(x, y);
for(i = 18; i >= 0; i--)
if(dep[x] - (1 << i) >= dep[y]){
up(res, D[x][i]); x = P[x][i];
}
if(x == y) return res;
for(i = 18; i >= 0; i--)
if(P[x][i] != P[y][i]){
up(res, D[x][i]); x = P[x][i];
up(res, D[y][i]); y = P[y][i];
}
up(res, D[x][0]); up(res, D[y][0]);
return res;
}
int main(){
scanf("%d%d%d%d", &R, &C, &V, &q);
for(i = 1; i <= R; i++) scanf("%s", m[i] + 1);
for(i = 1; i <= V; i++) a[i].scan();
bfs();
Kruskal();
for(i = 1; i <= V; i++)
if(!dep[i]){dep[i] = 1; dfs(i);}
for(; q; q--){
scanf("%d%d", &u, &v);
printf("%d\n", query(u, v));
}
return 0;
}
坑1：bfs 建立边的时候，记得去重，不然可能会有过多重边，去重时可以增加限制条件比如说 u < v 啊等等，又因为是 bfs，所以相同路径的同一条边会在一起出现，所以可以增加判 "上一条边" 去重，虽然还是有少量重边，但是优化已经很明显了，实际边数不超过 3n - 6 大概是 6 × 105，优化后 (带重边) 的边数也已经不超过两三百万，完全可以存下来。
坑2：无向图开边 × 2 不解释。
坑3：题解中已提到，如果无法到达，需要输出 -1，这可以在并查集中轻松得到，说句题外话，这好像是我第一次把并查集 (Union-Find) 给封装起来了，搞了一个 test 函数为询问是否在不同连通块并决定是否连接，具体见代码或模板。