题目描述
在麦克雷的面前出现了一个有n*m个格子的矩阵，每个格子用“.”或“#”表示，“.”表示这个格子可以放东西，“#”则表示这个格子不能放东西。现在他拿着一条1*2大小的木棒，好奇的他想知道对于一些子矩阵，有多少种放木棒的方案。
输入
第一行包含 2 个正整数 n，m。
接下来 n 行每行包含 m 个字符“.”或“#”。
第n+1行包含1个正整数q，表示询问次数。
接下来q行每行包含4个正整数r1，c1，r2，c2，分别表示询问的子矩阵的左上格子和右下格子的位置。
输出
输出共 q 行，每行包含 1 个整数，表示该询问的方案数。
样例输入
5 8
….#..#
.#……
##.#….
##..#.##
……..
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
样例输出
4
0
10
15
数据范围
30%：q<=100
100%：q<=10^5,1<=n,m<=500
样例解释
解法
把原问题转化为规定矩阵中有多少对相邻的“.”。
简单的前缀和问题。
代码
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define ln(x,y) int(log(x)/log(y))
#define sqr(x) ((x)*(x))
using namespace std;
const char* fin="aP2.in";
const char* fout="aP2.out";
const int inf=0x7fffffff;
const int maxn=507;
int n,m,i,j,k,l,o,ans;
char a[maxn][maxn];
int c[maxn][maxn][4],sum[maxn][maxn][7],d[maxn][maxn][4];
bool judge(int x,int y){
return x>0 && x<=n && y>0 && y<=m && a[x][y]=='.';
}
int getsum(int sx,int sy,int tx,int ty,int kind){
if (tx<sx || ty<sy) return 0;
return sum[tx][ty][kind]-sum[sx-1][ty][kind]-sum[tx][sy-1][kind]+sum[sx-1][sy-1][kind];
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%s",a[i]+1);
for (i=1;i<=n;i++) for (j=1;j<=m;j++){
if (judge(i,j)){
if (judge(i+1,j)){
c[i][j][0]++;
c[i][j][1]++;
sum[i][j][0]++;
sum[i][j][1]++;
sum[i][j][3]++;
sum[i][j][4]++;
sum[i][j][5]++;
d[i][j][0]++;
}
if (judge(i,j+1)){
c[i][j][0]++;
c[i][j][3]++;
sum[i][j][0]++;
sum[i][j][2]++;
sum[i][j][3]++;
sum[i][j][4]++;
sum[i][j][6]++;
d[i][j][3]++;
}
if (judge(i-1,j)){
c[i][j][2]++;
c[i][j][3]++;
sum[i][j][1]++;
sum[i][j][2]++;
sum[i][j][3]++;
sum[i][j][4]++;
sum[i][j][5]++;
d[i][j][2]++;
}
if (judge(i,j-1)){
c[i][j][1]++;
c[i][j][2]++;
sum[i][j][0]++;
sum[i][j][1]++;
sum[i][j][2]++;
sum[i][j][4]++;
sum[i][j][6]++;
d[i][j][1]++;
}
}
for (k=0;k<7;k++) sum[i][j][k]+=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];
}
scanf("%d",&i);
for (;i;i--){
scanf("%d%d%d%d",&j,&k,&l,&o);
if (j==l && k==o) ans=0;
else
if (j==l){
ans=getsum(j,k+1,j,o-1,6)+d[j][k][3]+d[j][o][1];
}else if (k==o) ans=getsum(j+1,o,l-1,o,5)+d[j][o][0]+d[l][o][2];
else {
ans=getsum(j+1,k+1,l-1,o-1,4)+c[j][k][0]+c[j][o][1]+c[l][k][3]+c[l][o][2];
ans+=getsum(j,k+1,j,o-1,0)+getsum(l,k+1,l,o-1,2);
ans+=getsum(j+1,o,l-1,o,1)+getsum(j+1,k,l-1,k,3);
}
ans/=2;
printf("%d
",ans);
}
return 0;
}启发
注意边界。