n*n预处理。
询问的时候用容斥，再删除边界。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=500+10; char s[maxn][maxn]; int n,m; int q; int p[maxn][maxn]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",s[i]); memset(p,0,sizeof p); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int num=0; if(s[i-1][j-1]=='.'){ if(s[i-1][j-2]=='.') num++; if(s[i-2][j-1]=='.') num++; p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+num; } else if(s[i-1][j-1]=='#'){ p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]; } } } scanf("%d",&q); for(int i=1;i<=q;i++){ int a,b,c,d; int ans=0; scanf("%d%d%d%d",&a,&b,&c,&d); ans=p[c][d]-p[c][b-1]-p[a-1][d]+p[a-1][b-1]; for(int i=a;i<=c;i++) if(s[i-1][b-1]=='.'&&s[i-1][b-2]=='.') ans--; for(int i=b;i<=d;i++) if(s[a-1][i-1]=='.'&&s[a-2][i-1]=='.') ans--; printf("%d ",ans); } return 0; }