← 返回题目列表

Codeforces · 475/C

C. Kamal-ol-molk 的画

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

有传言称 Kamal-ol-molk 的一幅画已被更改。矩形画笔已在画作上向右和向下移动。

将这幅画视为一个 n × m 的矩形网格。一开始,将 x × y 矩形画笔放置在框架中的某处,其边缘平行于框架,(1 ≤ x ≤ n,1 ≤ y ≤ m)。然后将刷子移动几次。每次画笔向右或向下移动一个单位。绘画过程中,画笔严格位于画框内。刷子会在某个时刻改变它所覆盖的每个单元格。

你找到了一幅老卡迈勒-奥尔莫克的画作。您想知道它是否可能已按所描述的方式进行了更改。如果是,您还想知道画笔的最小可能面积。

输入

输入的第一行包含两个整数n和m,(1≤n,m≤1000),表示画作的高度和宽度。

接下来的 n 行包含这幅画。每行有 m 个字符。字符“X”表示已更改的单元格,否则以“.”显示。这幅画中至少会有一个被改变的单元格。

输出

如果绘画可能被更改,则打印一行中画笔的最小面积,否则打印 - 1。

示例

输入 #1

4 4
XX..
XX..
XXXX
XXXX

输出 #1

4

输入 #2

4 4
....
.XXX
.XXX
....

输出 #2

2

输入 #3

4 5
XXXX.
XXXX.
.XX..
.XX..

输出 #3

-1