using namespace std;
#define maxn 1005
char s[maxn][maxn];
int match[maxn][maxn],sum[maxn][maxn];
int n;
struct {
int x,y,z;
bool operator <(const node &rhs)const {
return z>rhs.z;
}
} v[maxn*maxn];
int fa[maxn*maxn];
bool vis[maxn][maxn];
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
vector<int> g[maxn*maxn];
int ver[2*maxn*maxn],id[2*maxn*maxn],first[maxn*maxn];
int tot;
int dp[2*maxn*maxn][30];
void dfs(int root,int dep) {
ver[++tot]=root;
id[tot]=dep;
first[root]=tot;
for(int i=0; i<g[root].size(); i++) {
int v=g[root][i];
dfs(v,dep+1);
ver[++tot]=root;
id[tot]=dep;
}
}
void ST() {
for(int i=1; i<=tot; i++)
dp[i][0]=i;
for(int j=1; (1<<j)<=tot; j++) {
for(int i=1; i+(1<<j)-1<=tot; i++) {
int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
dp[i][j]=id[a]<id[b]?a:b;
}
}
}
int RMQ(int le,int ri) {
le=first[le],ri=first[ri];
if(le>ri) swap(le,ri);
int k=0;
while((1<<(k+1))<=ri-le+1) k++;
int a=dp[le][k],b=dp[ri-(1<<k)+1][k];
return id[a]<id[b]?ver[a]:ver[b];
}
int find(int x) {
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int init() {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='#');
}
}
for(int k=3; k<=n; k+=2) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(match[i][j]>=k-2&&match[i-1][j-1]>=k-2&&match[i-1][j+1]>=k-2
&&match[i+1][j-1]>=k-2&&match[i+1][j+1]>=k-2
&&match[i-1][j]>=k-2&&match[i+1][j]>=k-2
&&match[i][j-1]>=k-2&&match[i][j+1]>=k-2) match[i][j]=k;
}
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
int p=(i-1)*n+j-1;
v[p]=(node) {
i-1,j-1,match[i][j]
};
fa[p]=p;
g[p].clear();
vis[i-1][j-1]=false;
}
}
sort(v,v+n*n);
for(int i=0; i<n*n; i++) {
int x=v[i].x,y=v[i].y,z=v[i].z;
vis[x][y]=true;
for(int j=0; j<4; j++) {
int nx=x+dir[j][0],ny=y+dir[j][1];
if(nx<0||ny<0||ny>=n||nx>=n||!vis[nx][ny]) continue;
int fn=find(nx*n+ny);
if(fn==find(x*n+y)) continue;
g[x*n+y].push_back(fn);
fa[fn]=x*n+y;
}
}
return v[n*n-1].x*n+v[n*n-1].y;
}
int main() {
while(scanf("%d",&n)!=EOF) {
for(int i=1; i<=n; i++){
scanf("%s",s[i]+1);
for(int j=1;j<=n;j++){
if(s[i][j]=='#') match[i][j]=0;
else match[i][j]=1;
}
}
int root=init();
tot=0;
dfs(root,1);
ST();
int q;
scanf("%d",&q);
while(q--) {
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int r1=(x1-1)*n+y1-1;
int r2=(x2-1)*n+y2-1;
root=RMQ(r1,r2);
printf("%dn",match[root/n+1][root%n+1]);
}
}
return 0;
}
7
.....#.
...#.#.
....#..
....###
....#..
#......
.......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7
*/
近期评论