题目链接：http://codeforces.com/problemset/problem/611/C
题目大意
给定一个二维字符矩阵，和若干个查询，每次查询问子矩阵中可以有多少种1x2或是2x1矩阵的摆放方式
题目分析
先考虑DP转移方程，DP[i][j]表示(1,1),(i,j)矩阵中可以有多少种摆放方式,
状态转移：DP[i][j]=DP[i-1][j]+DP[i][j-1]+（i,j）坐标点与其相邻的满足条件的个数（偏左和偏上）。
画图模拟下不难发现这个方程，算一下边界有无重复度的情况即可，
那么对于查询的子矩阵，我们要考虑边界情况产生的重复度，就是有些在边界存在的小矩阵
没有被减去，遍历下边界即可，复杂度:O(n*q)。
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=6e2;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}char s[maxn][maxn];
int r,w;
int val[maxn][maxn],dp[maxn][maxn];
int solve(int x1,int y1,int x2,int y2){return s[x1][y1]=='.'&&s[x2][y2]=='.';
}
int main(){cin>>r>>w;rep(i,1,r+1) scanf("%s",s[i]+1);rep(i,1,w+1) dp[1][i]=solve(1,i,1,i-1)+dp[1][i-1];rep(i,1,r+1) dp[i][1]=solve(i,1,i-1,1)+dp[i-1][1];rep(i,2,r+1) rep(j,2,w+1) dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+solve(i,j,i-1,j)+solve(i,j,i,j-1);int q,x1,y1,x2,y2;cin>>q;while(q--){cin>>x1>>y1>>x2>>y2;x1--,y1--;int ans=dp[x2][y2]+dp[x1][y1]-dp[x2][y1]-dp[x1][y2];///cout<<dp[x2][y2]<<" "<<dp[x1][y1]<<" "<<dp[x2][y1]<<" "<<dp[x1][y2]<<endl;x1++,y1++;rep(i,x1,x2+1) ans-=solve(i,y1,i,y1-1);rep(i,y1,y2+1) ans-=solve(x1,i,x1-1,i);cout<<ans<<endl;}return 0;
}