← 返回题目列表

Codeforces · 1495/C

C. 太阳花园

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

太阳花园里有很多向日葵。

太阳花园是一张矩形表格,有 $$$n$$$ 行和 $$$m$$$ 列,表格的单元格是农田。所有的细胞都在其上长出一朵向日葵。不幸的是,有一天晚上,闪电击中了一些(可能是零个)细胞,那些细胞上的向日葵被烧成了灰烬。也就是说,那些被雷击中的牢房都变得空了。神奇的是,任何两个空单元格都没有公共点(既没有边缘也没有角)。

现在主人想要移除一些(可能是零)向日葵以达到以下两个目标:

- 当您位于空单元格时,您可以走到任何其他空单元格。换句话说,那些空单元格是相连的。
- 任意两个空单元格之间只有一条简单路径。换句话说,空单元之间没有循环。

如果它们有共同的边缘,您可以从一个空单元格走到另一个空单元格。

请问您能给业主一个满足她所有要求的解决方案吗?

请注意,不允许种植向日葵。您无需尽量减少移除的向日葵数量。可以证明答案总是存在的。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \le n,m \le 500$$$) — 行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符。每个字符都是“X”或“.”,分别代表一个空单元格和一个长出向日葵的单元格。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$250\,000$$$。

输出

对于每个测试用例,打印 $$$n$$$ 行。每个字符应包含 $$$m$$$ 字符,代表表的一行。每个字符应该是“X”或“.”,分别代表空单元格和带有向日葵的单元格。

如果有多个答案,您可以打印任何答案。可以证明答案总是存在的。

示例

输入 #1

5
3 3
X.X
...
X.X
4 4
....
.X.X
....
.X.X
5 5
.X...
....X
.X...
.....
X.X.X
1 10
....X.X.X.
2 2
..
..

输出 #1

XXX
..X
XXX
XXXX
.X.X
.X..
.XXX
.X...
.XXXX
.X...
.X...
XXXXX
XXXXXXXXXX
..
..

注意

让我们使用 $$$(x,y)$$$ 来描述第 $$$x$$$ 行和 $$$y$$$ 列的单元格。

在下面的图片中,白色、黄色和蓝色单元格分别代表长出向日葵的单元格、雷击的单元格和被移除的向日葵单元格。

在第一个测试用例中,一个可能的解决方案是删除 $$$(1,2)$$$、$$$(2,3)$$$ 和 $$$(3 ,2)$$$ 上的向日葵。

另一个可接受的解决方案是删除 $$$(1,2)$$$、$$$(2,2)$$$ 和 $$$(3,2)$$$ 上的向日葵。

该输出被认为是错误的,因为任何一对单元之间都有 2 条简单路径(存在循环)。例如,$$$(1,1)$$$ 和 $$$(3,3)$$$ 之间有 2 条简单路径。

1.$$$(1,1)\至(1,2)\至(1,3)\至(2,3)\至(3,3)$$$
2. $$$(1,1)\至 (2,1)\至 (3,1)\至 (3,2)\至 (3,3)$$$

此输出被认为是错误的,因为您无法从 $$$(1,1)$$$ 走到 $$$(3,3)$$$。