题目描述

在麦克雷的面前出现了一个有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\n",ans);

    }

    return 0;

}

启发

注意边界。