"#"代表不能放骨牌的地方,"."是可以放 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=;
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=; i<=n; ++i)
scanf("%s",s[i]+);
memset(a,,sizeof(a));
memset(b,,sizeof(b));
for(int i=; i<=n; ++i)
{
for(int j=; j<=m; ++j)
{
int k=;
if(s[i][j]=='.'&&s[i][j-]=='.')k=;
a[i][j]+=a[i][j-]+a[i-][j]-a[i-][j-]+k;
k=;
if(s[i-][j]=='.'&&s[i][j]=='.')k=;
b[i][j]+=b[i-][j]+b[i][j-]-b[i-][j-]+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-][r]+a[x-][y];
int t2=b[l][r]-b[l][y-]-b[x][r]+b[x][y-];
printf("%d\n",t1+t2);
}
}
return ;
}