← 返回题目列表

Codeforces · 745/B

B. 红牛解决了一个难题

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

红牛喜欢解谜。

有一天,红牛发现了两块一模一样的拼图,旁边有“做一个矩形”的说明。这些碎片可以用 n × m 的字符网格来描述,其中字符“X”表示拼图的一部分,“.”表示拼图的一部分。表示网格的空白部分。保证拼图块是一个 4 连通块。有关如何指定拼图的确切详细信息,请参阅输入格式和示例。

拼图块非常重,因此红牛无法旋转或翻转拼图块。然而,他可以将它们向任何方向移动。拼图块也不能重叠。

您将获得其中一件作品的描述作为输入。确定是否可以从给定输入的两个相同副本创建一个矩形。矩形应该是实心的,即其内部或边界上不应有空洞。请记住,红牛不允许翻转或旋转棋子,并且棋子不能重叠,即来自不同棋子的两个“X”不能共享相同的位置。

输入

输入的第一行将包含两个整数 n 和 m (1 ≤ n, m ≤ 500),即拼图的尺寸。

接下来的 n 行将描述拼图。每行的长度为 m 并且由字符“.”组成和仅“X”。 “X”对应于拼图的一部分“.”是一个空的空间。

保证输入中至少有一个“X”字符,并且“X”字符形成一个 4 连通区域。

输出

如果红牛可以制作矩形,则输出“YES”。否则输出“NO”。

示例

输入 #1

2 3
XXX
XXX

输出 #1

YES

输入 #2

2 2
.X
XX

输出 #2

NO

输入 #3

5 5
.....
..X..
.....
.....
.....

输出 #3

YES

注意

对于第一个示例,我们可以形成的矩形的一个示例如下

对于第二个样本,如果不旋转或翻转,就不可能将其中的两个块放置成一个矩形。

在第三个示例中,我们可以将第一个图块向右移动一位,然后组成以下矩形: