求助卡常

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
#define R register
struct EDGE{
	int v,w,last;
}Edge[1000005];
struct EDGE2{
	int u,v,w;
}Edge2[1000005];
struct NODE{
	int x,y;
};
int n;
int m;
int q;
int nn;
int cnt;
int ecnt;
int a[500005];
int p[500005];
int fa[500005];
int id[500005];
int in[500005];
int top[500005];
int dep[500005];
int son[500005];
int sig[500005];
int size[500005];
int b[1005][1005];
char s[1005][1005];
int st[500005][21];
int num[1005][1005];
int sum[1005][1005];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
inline void input(int &x){
	x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
}
void write(int x){
	if (x<10){
		putchar((char)(x+'0'));return;
	}
	write(x/10);
	putchar((char)(x%10+'0'));
}
inline void output(int x,char c){
	if (x<0) {putchar('-');x*=-1;}
	write(x);putchar(c);
}
inline void input2(int i){
	char c=getchar();
	while(c!='.'&&c!='#') c=getchar();
	int l=0;
	while(c=='.'||c=='#'){
		s[i][++l]=c;
		sum[i][l]=sum[i][l-1]+sum[i-1][l]-sum[i-1][l-1]+(c=='#');
		c=getchar();
	}
}
inline int min(int a,int b){
	return a<b?a:b;
}
bool cmp(EDGE2 _1,EDGE2 _2){
	return _1.w>_2.w;
}
inline void swap(int &a,int &b){
	int t=a;a=b;b=t;
}
inline void init(){
	ecnt=0;
	for (R int i(1);i<=nn;++i){
	    p[i]=-1;
	}
}
inline void insert(int u,int v,int w){
	Edge[++ecnt].v=v;
	Edge[ecnt].w=w;
	Edge[ecnt].last=p[u];
	p[u]=ecnt;
}
inline void init2(){
	for (R int i(1);i<=nn;++i){
		sig[i]=i;
	}
}
int get(int x){
	return x==sig[x]?x:sig[x]=get(sig[x]);
}
inline bool check(int x,int y,int l){
	int ux=x-l,dx=x+l;
	int ly=y-l,ry=y+l;
	if (ux<1||dx>n||ly<1||ry>n) return false;
	int res=sum[dx][ry]-sum[ux-1][ry]-sum[dx][ly-1]+sum[ux-1][ly-1];
	return !res;
}
inline void get_binary(int x,int y){
	int l=0,r=n;
	int res=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if (check(x,y,mid)){
			l=mid+1;res=mid;
		}
		else{
			r=mid-1;
		}
	}
	b[x][y]=res<<1|1;
}
inline void bfs(int x,int y){
	++nn;
	queue<NODE> q;
	q.push(NODE{x,y});
//	printf("%d:%d %d\n",nn,x,y);
	while(!q.empty()){
		NODE u=q.front();q.pop();
		int x=u.x,y=u.y;
		num[x][y]=nn;
		for (R int i(0);i<4;++i){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if (b[nx][ny]==b[x][y]&&(!num[nx][ny])){
				q.push(NODE{nx,ny});
			}
		}
	}
}
inline void Kruskal(){
	init();init2();
	sort(Edge2+1,Edge2+m+1,cmp);
	for (R int i(1);i<=m;++i){
		int u=Edge2[i].u;
		int v=Edge2[i].v;
		int w=Edge2[i].w;
		int fu=get(u),fv=get(v);
		if (fu!=fv){
			sig[fu]=fv;
//			printf("%d %d:%d\n",u,v,w);
			insert(u,v,w);insert(v,u,w);
		}
	}
}
inline void build(){
	for (R int i=1;i<=nn;i++){
		st[i][0]=a[i];
	}
	for (R int j(1);(1<<j)<=nn;++j){
		for (R int i(1);i<=nn;++i){
			if (i+(1<<j)-1>nn) break;
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
inline int query(int l,int r){
	int x=(int)log2(1.0*(r-l+1));
	return min(st[l][x],st[r-(1<<x)+1][x]);
}
void dfs1(int u,int f){
//	printf("%d %d\n",u,f);
	fa[u]=f;dep[u]=dep[f]+1;size[u]=1;
	for (R int i(p[u]);i!=-1;i=Edge[i].last){
		int v=Edge[i].v;
		int w=Edge[i].w;
		if (v==f) continue;
		dfs1(v,u);size[u]+=size[v];
		if (size[v]>size[son[u]]) son[u]=v;
		in[v]=w;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;id[u]=++cnt;a[cnt]=in[u];
	if (son[u]) dfs2(son[u],tp);
	for (R int i(p[u]);i!=-1;i=Edge[i].last){
		int v=Edge[i].v;
		if (v==son[u]||v==fa[u]) continue;
		dfs2(v,v);
	}
}
inline int query_tree(int u,int v){
	int res=inf;
	while(top[u]!=top[v]) {
		if (dep[top[u]]<dep[top[v]]) swap(u,v);
		res=min(res,query(id[top[u]],id[u]));
		u=fa[top[u]];
	}
	if (u!=v){
		if (dep[u]>dep[v]) swap(u,v);
		res=min(res,query(id[u]+1,id[v]));
	}
	return res;
}
int main(){
	input(n);
	for (R int i(1);i<=n;++i){
		input2(i);
	}
	for (R int i(1);i<=n;++i){
		for (R int j(1);j<=n;++j){
			get_binary(i,j);
//			output(b[i][j],' ');
		}
//		putchar('\n');
	}
//	putchar('\n');
	for (R int i(1);i<=n;++i){
		for (R int j(1);j<=n;++j){
			if (s[i][j]=='#') continue;
			if (!num[i][j]){
				bfs(i,j);
			}
		}
	}
	/*
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			output(num[i][j],' ');
		}
		putchar('\n');
	}
	//*/ 
	for (R int i=(1);i<=n;++i){
		for (R int j=(1);j<=n;++j){
			if (!num[i][j]) continue;
			for (R int k(0);k<2;++k){
				int ni=i+dx[k];
				int nj=j+dy[k];
				if (!num[ni][nj]) continue;
				if (num[i][j]==num[ni][nj]) continue;
				Edge2[++m]=EDGE2{num[i][j],num[ni][nj],min(b[i][j],b[ni][nj])};
			}
		}
	}
	Kruskal();
	for (R int i(1);i<=nn;++i){
		if (!id[i]){
			dfs1(i,0);dfs2(i,i);
		}
	}
	build();
	input(q);
	while(q--){
		int x1,y1,x2,y2;
		input(x1);input(y1);input(x2);input(y2);
		if (num[x1][y1]==num[x2][y2]) output(b[x1][y1],'\n');
		else output(query_tree(num[x1][y1],num[x2][y2]),'\n');
	}
	return 0;
}