太阳花园里有很多向日葵。
太阳花园是一张矩形表格,有 $$$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)$$$。