← 返回题目列表

Codeforces · 828/B

B. 黑色方块

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

Polycarp 有一张大小为 n × m 的方格纸。波利卡普将一些牢房涂成黑色,其他的则保持白色。受到马列维奇“黑色方块”的启发,波利卡普希望将尽可能少的白色单元格涂成黑色,以便所有黑色单元格形成一个正方形。

您需要确定需要涂成黑色的最小可能数量的单元格,以便黑色单元格形成一个黑色正方形,其边与绘画的边平行。所有不属于正方形的单元格都应该是白色的。正方形的边长应为正。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100) — 纸张的尺寸。

接下来的 n 行每行包含 m 个字母“B”或“W”——初始单元格颜色的描述。如果字母是“B”,则相应的单元格被漆成黑色,否则被漆成白色。

输出

打印需要涂成黑色的最小单元格数量,以便黑色单元格形成一个黑色正方形,其边与绘画的边平行。所有不属于正方形的单元格都应该是白色的。如果不可能,则打印-1。

示例

输入 #1

5 4
WWWW
WWWB
WWWB
WWBB
WWWW

输出 #1

5

输入 #2

1 2
BB

输出 #2

-1

输入 #3

3 3
WWW
WWW
WWW

输出 #3

1

注意

在第一个示例中,需要绘制 5 个单元格 — (2, 2)、(2, 3)、(3, 2)、(3, 3) 和 (4, 2)。那么就会有一个边长等于三的正方形,左上角在(2, 2)中。

在第二个示例中,所有单元格都涂成黑色并形成一个矩形,因此不可能得到正方形。

在第三个示例中,所有单元格都涂成白色,因此将任何单元格涂成黑色就足够了。