只保留极大的正方形然后逐行用并查集覆盖。

最慢1.38s。

#include<bits/stdc++.h>
using namespace std;
int a[2005][2005],S[2005][2005];
int sum(int x1,int y1,int x2,int y2){
	return S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];
}
vector<pair<int,int>> V[2005];
int mp[2005][2005];
struct dsu{
	int f[2005];
	int fd(int x){
		if(x==f[x]) return x;
		return f[x]=fd(f[x]); 
	}
}d[2005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=m;j++){
			a[i][j]=s[j-1]=='#';
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j]; 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			d[i].f[j]=j;
			int l=1,r=min(n-i+1,m-j+1);
			int res=0;
			while(l<=r){
				int mid=(l+r)/2;
				if(!sum(i,j,i+mid-1,j+mid-1)){
					l=mid+1;
					res=mid;
				}else{
					r=mid-1;
				}
			}
			if(i!=1&&j!=1&&!sum(i-1,j-1,i+res-1,j+res-1)) continue;
			if(res) V[res].push_back({i,j}); 
		}
		d[i].f[m+1]=m+1;
	}
	for(int sz=max(n,m);sz>=1;sz--){
		for(auto pos:V[sz]){
			int x=pos.first,y=pos.second;
			for(int i=x;i<=x+sz-1;i++){
				int j=d[i].fd(y);
				while(j<=y+sz-1){
					mp[i][j]=sz;
					d[i].f[j]=d[i].fd(j+1);
					j=d[i].fd(j+1);
				}
			}
		}
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		cout<<1ll*mp[x][y]*mp[x][y]<<"\n";
	}
}