← 返回题目列表

Codeforces · 525/D

D. 亚瑟和沃尔斯

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

终于有一天,亚瑟有足够的钱买一套公寓。他找到了一个靠近市中心且价格合理的绝佳选择。

亚瑟发现的公寓平面图看起来像一个由大小为 1 × 1 的正方形组成的 n × m 矩形。每个正方形都包含一面墙(此类正方形在平面图上用符号“*”表示)或自由空间(此类正方形在平面图上用符号“.”表示)。

公寓中的房间是由自由正方形组成的最大连通区域。如果正方形有公共边,则认为它们是相邻的。

亚瑟的老梦想是住在一套所有房间都是长方形的公寓里。他要求你计算为了实现这一目标需要拆除的最少墙壁数量。从正方形中移除墙壁后,它就变成了自由正方形。当拆除墙壁时,一些房间可能会合并成一个房间。

输入

输入的第一行包含两个整数 n, m (1 ≤ n, m ≤ 2000),表示 Arthur 公寓的大小。

接下来的 n 行每行包含 m 个符号——公寓的平面图。

如果单元格用符号“*”表示,则它包含一堵墙。

如果单元格用符号“.”表示那么这个牢房没有墙壁,而且这个牢房包含在一些房间里。

输出

输出 n 行,每行由 m 个符号组成,这些符号显示删除最小数量的墙壁以使每个房间(没有墙壁的最大连接区域)成为矩形后,亚瑟公寓平面图应是什么样子。

如果有多个可能的答案,则输出其中任何一个。

示例

输入 #1

5 5
.*.*.
*****
.*.*.
*****
.*.*.

输出 #1

.*.*.
*****
.*.*.
*****
.*.*.

输入 #2

6 7
***.*.*
..*.*.*
*.*.*.*
*.*.*.*
..*...*
*******

输出 #2

***...*
..*...*
..*...*
..*...*
..*...*
*******

输入 #3

4 5
.....
.....
..***
..*..

输出 #3

.....
.....
.....
.....