本文共 1243 字，大约阅读时间需要 4 分钟。

题意：给一个n行m列的由.和*组成的二维数组，横着的两个或者竖着的两个点点都符合条件，再给q对点（左上角和右下角）之间的矩形，然后问询问区间内符合条件的两连点有多少个。

一开始的想法就是枚举每一个点的竖着的两个和横着的两个是否符合，增加总和，但是写出来发现是一个三重循环，好吧，肯定超时

这里附上一张盗取的图，帮助了解二维前缀和，也可以自行去学习。

所以这个题最大的矩形前缀和就等于蓝的矩阵加上黄的矩阵，也就是横着加竖着再减去重叠面积，求出所有符合要求的情况。

#include 
   
    #include 
    
      using namespace std; char m[505][505];int a[505][505];int b[505][505]; int main(){    int h,w;    cin>>h>>w;    for(int i=1;i<=h;i++)    {        for(int j=1;j<=w;j++)        {            cin>>m[i][j];        }    }    for(int i=1;i<=h;i++)//利用公式预先求出所有情况    {        for(int j=1;j<=w;j++)        {            if(m[i][j]=='.' && m[i-1][j]=='.') a[i][j]++;            if(m[i][j]=='.' && m[i][j-1]=='.') b[i][j]++;            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//横着，并未加红色部分            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//竖着        }    }    int x1,y1,x2,y2,q;    cin>>q;    while(q--)//这样的直接用，就省了一重循环    {       int sum=0;        cin>>x1>>y1>>x2>>y2;        //加上红色部分        sum+=a[x2][y2]-a[x1][y2]-a[x2][y1-1]+a[x1][y1-1]；//横着        sum+=b[x2][y2]-b[x1-1][y2]-b[x2][y1]+b[x1-1][y1]；//竖着        cout<< sum <
    
   

转载地址：http://ztwzz.baihongyu.com/