CF525D Arthur and Walls

终于，Arthur 有足够的钱可以买一套公寓了。他在市中心附近找到了一处价格不错的房子。 Arthur 发现的公寓的平面图是一个 $n \times m$ 的矩形，由若干个 $1 \times 1$ 的小方格组成。每个小方格里要么是墙（在平面图上用符号“\*”表示），要么是空地（用符号“.”表示）。 公寓中的一个“房间”被定义为：由若干个相连的空地组成的最大连通区域。若两个格子有公共边，则它们相邻。 Arthur 一直梦想着能住进一套每个房间都是矩形的公寓。他希望你帮他计算，至少要移除多少堵墙才能实现这个目标。移除一堵墙后，该格子会变成空地。拆除时，原本分开的房间可能会合并成一个房间。

输入的第一行为两个整数 $n, m$，表示 Arthur 公寓的尺寸，满足 $1 \leq n, m \leq 2000$。 接下来的 $n$ 行，每行包含 $m$ 个字符，表示公寓的平面图。 如果某格为“\*”，则该格为墙。 如果为“.”，则该格为空地，属于某个房间。

输出 $n$ 行，每行 $m$ 个字符，表示 Arthur 公寓在删除最少数量的墙后，每个房间都是矩形时的平面图。 若有多组可能答案，输出任意一组均可。

由 ChatGPT 5 翻译