给你一张地图，给你q次询问，每次问你从A点到B点，最大能移动多大的箱子。
把每个点所能容纳的最大箱子求出来（BFS，八连通，一开始将所有边界点和障碍点入队）。然后从大到小排序。然后用并查集将相邻（四联通）的点依次链接起来，如果不路径压缩的话，那么两个节点的LCA的所能容纳的箱子大小就是答案。于是用并查集辅助建树，之后离线询问，然后Tarjan跑个LCA即可。
O(n^2+qlog(n))，log是因为map记录答案。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
using namespace std;
vector<int>ask[1010*1010];
int dx[]={0,1,0,-1,1,1,-1,-1},dy[]={1,0,-1,0,1,-1,1,-1};
int e,v[1010*1010],first[1010*1010],next[1010*1010];
void AddEdge(int U,int V){
v[++e]=V;
next[e]=first[U];
first[U]=e;
}
struct Point{
int x,y;
Point(const int &x,const int &y){
this->x=x;
this->y=y;
}
Point(){}
};
bool operator < (const Point &a,const Point &b){
return a.x!=b.x ? a.x<b.x : a.y<b.y;
}
map<Point,int>anss;
struct Node{
Point p;
int d;
Node(const Point &p,const int &d){
this->p=p;
this->d=d;
}
};
int n,siz[1010][1010],Siz[1010*1010],m,K;
int id[1010][1010];
bool cmp(const Point &a,const Point &b){
return siz[a.x][a.y]>siz[b.x][b.y];
}
char a[1010][1010];
queue<Node>q;
bool vis[1010][1010];
Point ps[1010*1010];
int fa[1010*1010];
int find(int x){
return x==fa[x] ? x : fa[x]=find(fa[x]);
}
Point qa[300010],qb[300010];
bool not_rt[1010*1010];
int ans[1010*1010];
bool VIS[1010*1010];
void LCA(int u)
{
ans[u]=u;
for(int i=first[u];i;i=next[i])
{
LCA(v[i]);
int f1=find(u),f2=find(v[i]);
fa[f1]=f2;
ans[find(u)]=u;
}
VIS[u]=true;
for(int i=0;i<ask[u].size();i++)
if(VIS[ask[u][i]]){
// printf("%d %d %d %d
",min(u,ask[u][i]),max(u,ask[u][i]),ans[find(ask[u][i])],Siz[ans[find(ask[u][i])]]);
anss[Point(min(u,ask[u][i]),max(u,ask[u][i]))]=Siz[ans[find(ask[u][i])]];
}
}
bool sb_q[300010];
int main(){
// freopen("h.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",a[i]+1);
}
for(int i=0;i<=n+1;++i){
q.push(Node(Point(i,0),0));
vis[i][0]=1;
q.push(Node(Point(i,n+1),0));
vis[i][n+1]=1;
}
for(int i=0;i<=n+1;++i){
q.push(Node(Point(0,i),0));
vis[0][i]=1;
q.push(Node(Point(n+1,i),0));
vis[n+1][i]=1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(a[i][j]=='#'){
q.push(Node(Point(i,j),0));
vis[i][j]=1;
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
id[i][j]=++m;
}
}
m=0;
while(!q.empty()){
Node U=q.front(); q.pop();
int x=U.p.x,y=U.p.y;
for(int i=0;i<8;++i){
int tx=x+dx[i],ty=y+dy[i];
if(tx>=1 && tx<=n && ty>=1 && ty<=n && !vis[tx][ty]){
q.push(Node(Point(tx,ty),U.d+1));
siz[tx][ty]=Siz[id[tx][ty]]=2*U.d+1;
vis[tx][ty]=1;
}
}
}
// for(int i=1;i<=n;++i){
// for(int j=1;j<=n;++j){
// printf("%d ",siz[i][j]);
// }
// puts("");
// }
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(siz[i][j]){
ps[++m]=Point(i,j);
}
}
}
for(int i=1;i<=m;++i){
fa[id[ps[i].x][ps[i].y]]=id[ps[i].x][ps[i].y];
}
sort(ps+1,ps+m+1,cmp);
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;++i){
int x=ps[i].x,y=ps[i].y;
for(int j=0;j<4;++j){
int tx=x+dx[j],ty=y+dy[j];
if(a[tx][ty]=='.' && vis[tx][ty]){
int rt=find(id[tx][ty]);
if(rt!=find(id[x][y])){
AddEdge(id[x][y],rt);
// printf("%d %d
",id[x][y],rt);
not_rt[rt]=1;
fa[rt]=id[x][y];
}
}
}
vis[x][y]=1;
}
scanf("%d",&K);
for(int i=1;i<=K;++i){
scanf("%d%d%d%d",&qa[i].x,&qa[i].y,&qb[i].x,&qb[i].y);
int f1=find(id[qa[i].x][qa[i].y]),f2=find(id[qb[i].x][qb[i].y]);
if(f1==f2){
ask[id[qa[i].x][qa[i].y]].push_back(id[qb[i].x][qb[i].y]);
ask[id[qb[i].x][qb[i].y]].push_back(id[qa[i].x][qa[i].y]);
}
else{
sb_q[i]=1;
}
}
for(int i=1;i<=m;++i){
fa[id[ps[i].x][ps[i].y]]=id[ps[i].x][ps[i].y];
}
for(int i=1;i<=m;++i){
if(!not_rt[id[ps[i].x][ps[i].y]]){
LCA(id[ps[i].x][ps[i].y]);
}
}
for(int i=1;i<=K;++i){
if(sb_q[i]){
puts("0");
}
else{
printf("%d
",anss[Point(min(id[qa[i].x][qa[i].y],id[qb[i].x][qb[i].y]),
max(id[qa[i].x][qa[i].y],id[qb[i].x][qb[i].y]))]);
}
}
return 0;
}