D. White Lines

题目
D. White Lines
time limit per test1.5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of nn rows and nn columns of square cells. The rows are numbered from 11 to nn, from top to bottom, and the columns are numbered from 11 to nn, from left to right. The position of a cell at row rr and column cc is represented as (r,c)(r,c). There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size kk (1≤k≤n1≤k≤n). To use the eraser, Gildong needs to click on a cell (i,j)(i,j) where 1≤i,j≤n−k+11≤i,j≤n−k+1. When a cell (i,j)(i,j) is clicked, all of the cells (i′,j′)(i′,j′) where i≤i′≤i+k−1i≤i′≤i+k−1 and j≤j′≤j+k−1j≤j′≤j+k−1 become white. In other words, a square with side equal to kk cells and top left corner at (i,j)(i,j) is colored white.

A white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.

Input
The first line contains two integers nn and kk (1≤k≤n≤20001≤k≤n≤2000) — the number of rows and columns, and the size of the eraser.

The next nn lines contain nn characters each without spaces. The jj-th character in the ii-th line represents the cell at (i,j)(i,j). Each character is given as either ‘B’ representing a black cell, or ‘W’ representing a white cell.

Output
Print one integer: the maximum number of white lines after using the eraser exactly once.

Examples
inputCopy
4 2
BWWW
WBBW
WBBW
WWWB
outputCopy
4
inputCopy
3 1
BWB
WWB
BWB
outputCopy
2
inputCopy
5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW
outputCopy
2
inputCopy
2 2
BW
WB
outputCopy
4
inputCopy
2 1
WW
WW
outputCopy
4
Note
In the first example, Gildong can click the cell (2,2)(2,2), then the working screen becomes:

BWWW
WWWW
WWWW
WWWB
Then there are four white lines — the 22-nd and 33-rd row, and the 22-nd and 33-rd column.

In the second example, clicking the cell (2,3)(2,3) makes the 22-nd row a white line.

In the third example, both the 22-nd column and 55-th row become white lines by clicking the cell (3,2)(3,2).

题意：从（i，j）处向右向下消除长为k的方块（消除后k*k方块内都为‘W’），最多能有几行几列‘W’。

思路：暴力做超时了。借鉴博客。
预处理操作，找到消除（i，j）处时能新产生多少白线行、列。
sumr[i][j] :第i行前j列‘B’的数量
sumc[i][j] :第j列前i行‘B’的数量
r[i][j] ： 在（i，j）处消除第i行能否成为白线行
c[i][j] :在（i，j）处消除第j列能否成为白线列
ansr[i][j] :i行及以前产生的新白线行的数量
ansc[i][j] :j列及以前产生的新白线列的数量

/**/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010;
int sumr[N][N],sumc[N][N],r[N][N],c[N][N],ansr[N][N],ansc[N][N];
char s[N][N];
int main()
{
    int n,k,i,j;
    int pre_sum=0;
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        cin>>s[i];
        for(j=0;j<n;j++)
        {
            if(s[i][j]=='B')
            {
                sumr[i][j]=sumr[i][j-1]+1;
                sumc[i][j]=sumc[i-1][j]+1;
            }
            else
            {
                sumr[i][j]=sumr[i][j-1];
                sumc[i][j]=sumc[i-1][j];
            }
        }
    }
    for(i=0;i<n;i++)
    {
        if(sumr[i][n-1]==0)
            pre_sum++;
    }
    for(i=0;i<n;i++)
    {
        if(sumc[n-1][i]==0)
            pre_sum++;
    }
    for(i=0;i<n;i++)//使从j到j+k-1成为白块，看i行能否成为新的白线行
    {
        for(j=0;j<n-k+1;j++)
        {
            if(sumr[i][n-1]!=0)
            {
                if(sumr[i][n-1]==sumr[i][j+k-1]-sumr[i][j-1])//看消除的‘B’是不是i行所有的‘B’
                r[i][j]=1;
            }
        }
    }
    for(j=0;j<n;j++)
    {
        for(i=0;i<n-k+1;i++)
        {
            if(sumc[n-1][j]!=0)
            {
                if(sumc[n-1][j]==sumc[i+k-1][j]-sumc[i-1][j])
                c[i][j]=1;
            }
        }
    }
    for(i=0;i<n;i++)//i行及i行前产生的新的白线行、列
    {
        for(j=0;j<n;j++)
        {
            ansr[i][j]+=ansr[i-1][j]+r[i][j];
            ansc[i][j]+=ansc[i][j-1]+c[i][j];
        }
    }
    int ans=0;
    for(i=0;i<n-k+1;i++)//在（i，j）处消除产生的新白线行、列
    {
        for(j=0;j<n-k+1;j++)
        {
            ans=max(ans,ansr[i+k-1][j]-ansr[i-1][j]+ansc[i][j+k-1]-ansc[i][j-1]);
        }
    }
    ans+=pre_sum;
    cout<<ans<<endl;
    return 0;
}