TLE 40pts 求调

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}
const int N=1005,K=1e6+5;
int n;
char ch[N][N];
int sum[N][N];
bool Check(int x,int y,int k){
	if(k>=x||k>=y||x+k>n||y+k>n) return 0;
	if(sum[x+k][y+k]-sum[x-k-1][y+k]-sum[x+k][y-k-1]+sum[x-k-1][y-k-1]>=1) return 0;
	return 1;
}
int dx[4]={0,0,-1,1},dy[4]={-1,1};
int dis[N][N];
int tote;
struct Edge{
	int u,v,w;
}e[K*4];
int Id(int x,int y){
	return (x-1)*n+y;
}
int fa[K];
bool Cmp(Edge x,Edge y){
	return x.w>y.w;
}
int Find(int x){
	if(x==fa[x]) return x;
	return Find(fa[x]);
}
struct Node{
	int v,w;
};
vector<Node>mp[K];
void Kruskal(){
	for(int i=1;i<=n*n;i++) fa[i]=i;
	sort(e+1,e+tote+1,Cmp);
	for(int i=1;i<=tote;i++){
		int u=Find(e[i].u),v=Find(e[i].v);
		if(u==v) continue;
		mp[u].push_back({v,e[i].w});
		mp[v].push_back({u,e[i].w});
		fa[u]=v;
	}
}
int Idx(int x){
	return (x-1)/n+1;
}
int Idy(int x){
	if(x%n==0) return n;
	return x%n;
}
int dep[K];
int st[K][21],val[K][21];
void Dfs(int u,int f){
	dep[u]=dep[f]+1;
	st[u][0]=f;
	val[u][0]=min(dis[Idx(u)][Idy(u)],dis[Idx(f)][Idy(f)]);
	for(int i=1;i<=20;i++){
		st[u][i]=st[st[u][i-1]][i-1];
		val[u][i]=min(val[u][i-1],val[st[u][i-1]][i-1]);
	}
	for(Node node:mp[u]){
		int v=node.v;
		if(v==f) continue;
		Dfs(v,u);
	}
}
int Lca(int u,int v){
	int minl=min(dis[Idx(u)][Idy(u)],dis[Idx(v)][Idy(v)]);
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=20;i>=0;i--)
		if(dep[st[u][i]]>=dep[v]){
			minl=min(minl,val[u][i]);
			u=st[u][i];
		}
	if(u==v) return minl;
	for(int i=20;i>=0;i--)
		if(st[u][i]-st[v][i]){
			minl=min(minl,val[u][i]);
			minl=min(minl,val[v][i]);
			u=st[u][i];
			v=st[v][i];
		}
	return minl;
}
void Solve(){
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>ch[i][j];
			sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
			if(ch[i][j]=='#')
				sum[i][j]++;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			int l=-1,r=n/2;
			while(l<r-1){
				int mid=l+r>>1;
				if(Check(i,j,mid)) l=mid;
				else r=mid;
			}
			dis[i][j]=2*l+1;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=0;k<=3;k++){
				int x=i+dx[k],y=j+dy[k];
				if(x>=1&&y>=1&&x<=n&&y<=n&&ch[i][j]=='.'&&ch[x][y]=='.')
					e[++tote]={Id(i,j),Id(x,y),min(dis[i][j],dis[x][y])};
			}
	Kruskal();
	for(int i=1;i<=n*n;i++)
		if(!dep[i]&&ch[Idx(i)][Idy(i)]=='.')
			Dfs(i,0);
	int q=read();
	#define y1 Y1
	while(q--){
		int x1=read(),y1=read(),x2=read(),y2=read();
		if(Find(Id(x1,y1))-Find(Id(x2,y2)))
			cout<<"0\n";
		else cout<<Lca(Id(x1,y1),Id(x2,y2))<<"\n";
	}
}
int main(){
	int T=1;
	while(T--) Solve();
	return 0;
}