给你 $$$n \times m$$$ 网格。有些单元格被填满,有些单元格是空的。
城市是填充单元格的最大(通过包含)集合,因此可以通过移动到相邻(并排)单元格从集合中的任何单元格到达集合中的任何其他单元格,而无需移动到集合中不存在的任何单元格。换句话说,城市是填充单元格的连接组件,相邻(并排)单元格之间具有边缘。
最初,网格上有两个城市。您想要将一些空单元格更改为填充单元格,以便满足以下两个条件:
- 结果网格上有一个城市。
- 任何两个填充单元之间的最短路径(只能通过移动到填充单元上才能实现)等于它们之间的曼哈顿距离。
两个像元 $$$(a, b)$$$ 和 $$$(c, d)$$$ 之间的曼哈顿距离等于 $$$|a - c| + |b - d|$$$。
找到一种方法来添加满足这些条件的填充单元格,并最大限度地减少填充单元格的总数。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$,即测试用例的数量 ($$$1 \le t \le 5000$$$)。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 50$$$, $$$nm \geq 3$$$)。
接下来的 $$$n$$$ 行描述了网格。第 $$$i$$$ 行包含长度为 $$$m$$$ 的字符串 $$$s_i$$$。如果 $$$(i, j)$$$ 位置的单元格已填充,则 $$$s_{i,j}$$$ 为“#”,并且为“.”如果它是空的。
保证初始网格中恰好有两个城市。
保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$25\,000$$$。
输出
对于每个测试用例,输出 $$$n$$$ 行,每行包含一个长度为 $$$m$$$ 的字符串,描述您以与输入相同的格式创建的网格。
如果有多个可能的答案,并且填充单元格的数量最少,则打印其中一个。
示例
输入 #1
11 1 3 #.# 2 2 .# #. 4 4 ..## ...# #... ##.. 6 6 .##... ##.... ...... ....## .....# ...### 6 5 .#..# .#..# .#..# .#.## .#... ##... 5 5 ##### #...# #.#.# #...# ##### 4 4 .##. ##.# #.## .##. 5 5 ..### ....# ..... #.... #.... 5 6 .##... ##.... #....# ....## ...##. 6 5 ..##. ...## ....# #.... ##... .##.. 5 4 ..## ..#. ..#. #... #...
输出 #1
### .# ## ..## ..## ###. ##.. .##... ###... ..#... ..#### ...### ...### .#### .#### .#### .#### .#... ##... ##### ##### ##### ##### ##### .##. #### #### .##. ..### ..### ..#.. ###.. #.... .##... ###... ###### ...### ...##. ..##. ..### ..### ###.. ###.. .##.. ..## ..#. ..#. ###. #...
注意
在第一个测试用例中,我们可以在两个城市之间添加一个填充单元格来连接它们。我们可以验证第二个条件是否满足。
在第二个测试用例中,我们还可以使用单个填充单元格连接城市,同时满足第二个条件。
在第三个测试用例中,请注意,如果我们填充左上角的 3 个单元格,城市将被连接,但单元格 $$$(4, 2)$$$ 和 $$$(2, 4)$$$ 将不满足第二个条件。