CF1200D-DIV2-578-二维前缀和、二维滑动窗口

wflengxuenong · 2022-09-30 11:16:07 · 个人记录

#include <bits/stdc++.h>
const int N = 2e3 + 10;
using namespace std;

char s[N][N];
int sum[N][N];
//二维滑动窗口。单点修改，区间查询。 
int main() {
    int n,k;
    cin >> n >> k;
    for(int i=1; i<=n; ++i) 
        scanf("%s",s[i]+1);
    for(int i=1; i<=n; ++i) {
        int l=0,r=0;//找出一行中B的左右端点，如果>k处理这行也没用。否则，处理包含这段区间的k*k区域。 
        for(int j=1; j<=n; ++j) {
            if(s[i][j]=='B') {
                if(l==0)
                    l=j,r=j;
                else
                    r=j;
            }
        }
        if(l==0) {
            sum[1][1]++;
            continue;
        }
        if(r-l+1>k)
            continue;
        int x1=max(1,i-k+1),y1=max(1,r-k+1),x2=i,y2=l;
        sum[x1][y1]++,sum[x1][y2+1]--,sum[x2+1][y2+1]++,sum[x2+1][y1]--;
    }
    for(int i=1; i<=n; ++i) {//同样的方法处理列 
        int u=0,d=0;
        for(int j=1; j<=n; ++j) {
            if(s[j][i]=='B') {
                if(u==0)
                    u=j,d=j;
                else
                    d=j;
            }
        }
        if(u==0) {
            sum[1][1]++;
            continue;
        }
        if(d-u+1>k)
            continue;
        int x1=max(1,d-k+1),y1=max(1,i-k+1),x2=u,y2=i;
        sum[x1][y1]++,sum[x1][y2+1]--,sum[x2+1][y2+1]++,sum[x2+1][y1]--;
    }
    int ans=0;
    for(int i=1; i<=n; ++i) {//查询二维区间最大值。 
        for(int j=1; j<=n; ++j) {
            sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
            ans=max(ans,sum[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}