题目（权限题）
Description
JOI君所居住的IOI市以一年四季都十分炎热著称。
IOI市是一个被分成纵H*横W块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有P个，编号为1…P。
JOI君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。
JOI君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要1单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此IOI市的市民一般都携带水壶出行。大小为x的水壶最多可以装x单位的水，建筑物里有自来水可以将水壶装满。
由于携带大水壶是一件很困难的事情，因此JOI君决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。
现在给出IOI市的地图和Q个询问，第i个询问(1<=i<=Q)为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”，请你对于每个询问输出对应的答案。
Input
第一行四个空格分隔的整数H,W,P,Q，表示IOI市被分成了纵H*横W块区域，有P个建筑物，Q次询问。
接下来H行，第i行(1<=i<=H)有一个长度为W的字符串，每个字符都是’.’或’#’之一，’.’表示这个位置是建筑物或原野，’#’表示这个位置是墙壁。
接下来P行描述IOI市每个建筑物的位置，第i行(1<=i<=P)有两个空格分隔的整数Ai和Bi，表示第i个建筑物的位置在第Ai行第Bi列。保证这个位置在地图中是’.’
接下来Q行，第i行(1<=i<=Q)有两个空格分隔的整数Si和Ti，表示第i个询问为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”
Output
输出Q行，第i行(1<=i<=Q)一个整数，表示在建筑物Si和Ti之间移动最小需要多大的水壶。
如果无法到达，输出-1。此外，如果不需要经过原野就能到达，输出0。
Sample Input
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4
Sample Output
3
4
4
2
HINT
1<=H<=2000
1<=W<=2000
2<=P<=2*10^5
1<=Q<=2*10^5
1<=Ai<=H(1<=i<=P)
1<=Bi<=W(1<=i<=P)
(Ai,Bi)≠(Aj,Bj)(1<=i<j<=P)
1<=Si<Ti<=P(1<=i<=Q)
题解
假设我们能搞出城市之间的边了，剩下的就是重构树裸题了
怎么搞边呢？
$bfs$每个城市将附近的原野染色，每个原野记录最近的城市为谁（即颜色）和到最近的城市的距离
如果从$i$城市到达了$j$原野并且$j$原野没染色，就把$j$原野染成$i$；如果已经染色并且颜色为$k$，就求出了$i$到$k$之间的距离（即$i\rightarrow j+k\rightarrow j$）
因为边长不超过$H*W$，所以可以用$vector$存每个边，这样就不用$sort$了
这题卡常卡到恶心（$bzoj$6元CPU果然虚），原来我用$string$存的字符串，后面改成$char[]$就过了QAQ
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<queue>
# include<algorithm>
using namespace std;
const int MAX=4e5+5,MAXN=2e3+5;
struct p{
int x,y;
}c[MAX],point[MAX];
int n,m,num,tot,cnt,P,Q;
int mv1[4]={1,-1,0,0};
int mv2[4]={0,0,1,-1};
int h[MAX],fa[MAX],val[MAX],d[MAX];
int col[MAXN][MAXN],dis[MAXN][MAXN],f[MAX][22];
char A[MAXN][MAXN];
queue<p> qu;
vector<p> ve[MAX*10];
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void bfs()
{
while(!qu.empty())
{
p tt=qu.front();
qu.pop();
for(int i=0;i<=3;++i)
{
int xx=tt.x+mv1[i],yy=tt.y+mv2[i];
if(A[xx][yy]=='#'||xx<1||yy<1||xx>n||yy>m) continue;
if(!col[xx][yy]) qu.push((p){xx,yy}),col[xx][yy]=col[tt.x][tt.y],dis[xx][yy]=dis[tt.x][tt.y]+1;
else ve[dis[xx][yy]+dis[tt.x][tt.y]].push_back((p){col[xx][yy],col[tt.x][tt.y]});
}
}
}
int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
}
void dfs(int x,int f)
{
d[x]=d[f]+1;
for(int i=h[x];i;i=c[i].x)
dfs(c[i].y,x);
}
int LCA(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
for(int i=21;i>=0;--i)
if(d[f[x][i]]>=d[y]) x=f[x][i];
if(x==y) return x;
for(int i=21;i>=0;--i)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
n=read(),m=read(),cnt=P=read(),Q=read();
for(int i=1;i<=n;++i)
scanf("%s",A[i]+1);
for(int i=1;i<=P;++i)
fa[i]=i,point[i].x=read(),point[i].y=read(),col[point[i].x][point[i].y]=i,qu.push(point[i]);
bfs();
int Num=0;
for(int i=0;i<=n*m;++i)
{
if(Num==P-1) break;
for(int j=0;j<ve[i].size();++j)
{
int r1=find(ve[i][j].x),r2=find(ve[i][j].y);
if(r1==r2) continue;
++Num,val[++cnt]=i,fa[cnt]=fa[r1]=fa[r2]=cnt,f[r1][0]=f[r2][0]=cnt;
add(cnt,r1),add(cnt,r2);
}
}
for(int i=1;i<=21;++i)
for(int j=1;j<=cnt;++j)
f[j][i]=f[f[j][i-1]][i-1];
for(int i=cnt;i>=1;--i)
if(!d[i]) dfs(find(i),0);
for(int i=1;i<=Q;++i)
{
int x=read(),y=read();
if(find(x)!=find(y)) printf("-1\n");
else printf("%d\n",val[LCA(x,y)]);
}
return 0;
}
