"#"代表不能放骨牌的地方，"."是可以放 500*500的矩阵，q次询问
开两个dp数组，a,b,a统计横着放的方案数，b表示竖着放，然后询问时O(1)的，容斥一下， 复杂度O（n^2+q)
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cstdlib> #include<cmath> #include<cstdlib> #include<vector> #include<queue> using namespace std; typedef long long LL; const int maxn=505; int a[maxn][maxn]; int b[maxn][maxn]; char s[maxn][maxn]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=n; ++i) scanf("%s",s[i]+1); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { int k=0; if(s[i][j]=='.'&&s[i][j-1]=='.')k=1; a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+k; k=0; if(s[i-1][j]=='.'&&s[i][j]=='.')k=1; b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+k; } } int q; scanf("%d",&q); while(q--) { int x,y,l,r; scanf("%d%d%d%d",&x,&y,&l,&r); int t1=a[l][r]-a[l][y]-a[x-1][r]+a[x-1][y]; int t2=b[l][r]-b[l][y-1]-b[x][r]+b[x][y-1]; printf("%d ",t1+t2); } } return 0; }