← 返回题目列表

Codeforces · 1799/E

E. 城市联盟

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

给你 $$$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)$$$ 将不满足第二个条件。