← 返回题目列表

Codeforces · 1200/D

D. 白线

中文机器翻译题面 查看原题

Gildong买了一个著名的绘画软件cfpaint。 cfpaint 的工作屏幕是方形的,由 $$$n$$$ 行和 $$$n$$$ 列方形单元格组成。行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。 $$$r$$$ 行和 $$$c$$$ 列的单元格位置表示为 $$$(r, c)$$$。 cfpaint 中的单元格只有两种颜色:黑色和白色。

cfpaint中有一个名为橡皮擦的工具。橡皮擦的大小为整数 $$$k$$$ ($$$1 \le k \le n$$$)。要使用橡皮擦,Gildong 需要单击单元格 $$$(i, j)$$$,其中 $$$1 \le i, j \le n - k + 1$$$。单击单元格 $$$(i, j)$$$ 时,所有单元格 $$$(i', j')$$$(其中 $$$i \le i' \le i + k - 1$$$ 和 $$$j \le j' \le j + k - 1$$$ 都会变成白色。换句话说,边长等于 $$$k$$$ 个单元且左上角位于 $$$(i, j)$$$ 的正方形被涂成白色。

白线是没有任何黑色单元的行或列。

Gildong 使用 cfpaint 已经有一段时间了,因此某些单元格(可能为零或全部)当前是黑色的。他想知道使用橡皮擦一次后最多能画出多少条白线。帮助吉尔东找到问题的答案。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2000$$$) — 行数和列数以及橡皮擦的大小。

接下来的 $$$n$$$ 行包含 $$$n$$$ 个字符,每个字符不带空格。第 $$$i$$$ 行中的第 $$$j$$$ 字符表示 $$$(i,j)$$$ 处的单元格。每个字符都以“B”表示黑色单元格或“W”表示白色单元格。

输出

打印一个整数:使用橡皮擦一次后的最大白线数。

示例

输入 #1

4 2
BWWW
WBBW
WBBW
WWWB

输出 #1

4

输入 #2

3 1
BWB
WWB
BWB

输出 #2

2

输入 #3

5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW

输出 #3

2

输入#4

2 2
BW
WB

输出#4

4

输入 #5

2 1
WW
WW

输出 #5

4

注意

在第一个示例中,Gildong 可以单击单元格 $$$(2, 2)$$$,然后工作屏幕变为:

然后有四根白线 - $$$2$$$-nd 和 $$$3$$$-rd 行,以及 $$$2$$$-nd 和 $$$3$$$-rd 列。

在第二个示例中,单击单元格 $$$(2, 3)$$$ 会使 $$$2$$$-nd 行成为一条白线。

在第三个示例中,通过单击单元格 $$$(3, 2)$$$,第 $$$2$$$ 列和第 $$$5$$$ 行都变成白线。