White Lines

主要思路就是利用差分

对于行：如果在某一个点上，向右下角涂掉 k*k 的矩形能够使得新出现一行 “B” 那么就在这个点上 +1（这里的加 +1 需要利用差分来完成）

列同理，如果有现成的空白行，记录一下即可，最后直接加上

代码：

// Created by CAD on 2019/8/12.

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

char g[2005][2005];

int a[2005][2005];

int b[2005][2005];

void dif(int x1,int y1,int x2,int y2)

{

    a[x1][y1]++,a[x2][y2]++;

    a[x1][y2]--,a[x2][y1]--;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n,k;cin>>n>>k;

    int ok=0;

    for(int i=1;i<=n;++i)

        for(int j=1;j<=n;++j)

            cin>>g[i][j];

    for(int i=1;i<=n;++i)

    {

        int maxn=0,minn=0;

        for(int j=1;j<=n;++j)

        {

            if(g[i][j]=='B')

            {

                maxn=j;

                if(!minn)

                    minn=j;

            }

        }

        if(minn==0)  ok++;

        else if(maxn-minn+1<=k)

            dif(max(0,i-k)+1,max(0,maxn-k)+1,i+1,minn+1);

    }

    for(int j=1;j<=n;++j)

    {

        int maxn=0,minn=0;

        for(int i=1;i<=n;++i)

        {

            if(g[i][j]=='B')

            {

                maxn=i;

                if(!minn) minn=i;

            }

        }

        if(minn==0) ok++;

        else if(maxn-minn+1<=k) dif(max(0,maxn-k)+1,max(0,j-k)+1,minn+1,j+1);

    }

    ll ans=0;

    for(int i=1;i<=n;++i)

    {

        for(int j=1;j<=n;++j)

        {

            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];

            ans=max(ans,1ll*a[i][j]+ok);

        }

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

White Lines

最新文章

热门文章