White Lines
InterviewTime limit1.5sMemory limit256 MB
Given an n by n grid of black and white cells, paint one k by k square white to maximize the number of fully white rows and columns.
- Level
Medium5 of 10
- Topics
- Prefix sum, Matrix, Implementation
- Solved
- No attempts yet
Problem
Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is a square of rows and columns of cells. Rows are numbered 1 to from top to bottom, and columns are numbered 1 to from left to right. The cell at row and column is written . Each cell is either black or white.
The eraser tool has an integer size (). To use it, Gildong clicks a cell with . Every cell with and becomes white. In other words, the square of side with top left corner is painted white.
A white line is a row or column with no black cells.
Gildong has used cfpaint for a while, so some cells (possibly none or all) are black now. Find the maximum number of white lines after using the eraser exactly once.
Input
The first line has two integers and (), the number of rows and columns and the eraser size. The next lines each contain characters without spaces. The -th character of the -th line is the cell : 'B' for black, 'W' for white.
Output
Print one integer: the maximum number of white lines that can be obtained after using the eraser exactly once.
Hint
In the first example, Gildong can click cell . The screen then becomes:
BWWW
WWWW
WWWW
WWWB
There are four white lines: rows 2 and 3, and columns 2 and 3.
In the second example, clicking cell makes row 2 a white line.
In the third example, clicking cell makes both column 2 and row 5 white lines.