CF475C.Kamal-ol-molk's Painting
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Rumors say that one of Kamal-ol-molk's paintings has been altered. A rectangular brush has been moved right and down on the painting.
Consider the painting as a n × m rectangular grid. At the beginning an x × y rectangular brush is placed somewhere in the frame, with edges parallel to the frame, (1 ≤ x ≤ n, 1 ≤ y ≤ m). Then the brush is moved several times. Each time the brush is moved one unit right or down. The brush has been strictly inside the frame during the painting. The brush alters every cell it has covered at some moment.
You have found one of the old Kamal-ol-molk's paintings. You want to know if it's possible that it has been altered in described manner. If yes, you also want to know minimum possible area of the brush.
传言称,卡马尔-奥尔-莫尔克(Kamal-ol-molk)的一幅画作曾被篡改:一个矩形画刷在画作上向右和向下移动过。
将画作视为一个 n×m 的矩形网格。初始时,一个 x×y 的矩形画刷被放置于画框内的某处,其边与画框平行(其中 1≤x≤n,1≤y≤m)。随后,画刷进行了若干次移动;每次移动一格,方向仅为向右或向下。在整个绘制过程中,画刷始终严格位于画框内部。画刷在运动过程中所覆盖过的每一个格子均被篡改。
你发现了一幅卡马尔-奥尔-莫尔克的旧画作。你想判断:它是否可能以如上所述的方式被篡改?若可能,你还希望求出画刷的最小可能面积。
输入格式
The first line of input contains two integers n and m, (1 ≤ n, m ≤ 1000), denoting the height and width of the painting.
The next n lines contain the painting. Each line has m characters. Character 'X' denotes an altered cell, otherwise it's showed by '.'. There will be at least one altered cell in the painting.
输入的第一行包含两个整数 n 和 m(1 ≤ n, m ≤ 1000),分别表示画作的高度和宽度。
接下来的 n 行描述该画作。每行包含 m 个字符。字符 'X' 表示被修改过的单元格,其余单元格用 '.' 表示。画作中至少存在一个被修改过的单元格。
输出格式
Print the minimum area of the brush in a line, if the painting is possibly altered, otherwise print - 1.
如果绘画可能被修改,则在一行中输出画笔的最小面积;否则输出 -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
输入解题思路,AI测评打分。不知道怎么写?