CF1799E.City Union

You are given $n \times m$ grid. Some cells are filled and some are empty.

A city is a maximal (by inclusion) set of filled cells such that it is possible to get from any cell in the set to any other cell in the set by moving to adjacent (by side) cells, without moving into any cells not in the set. In other words, a city is a connected component of filled cells with edges between adjacent (by side) cells.

Initially, there are two cities on the grid. You want to change some empty cells into filled cells so that both of the following are satisfied:

• There is one city on the resulting grid.
• The shortest path between any two filled cells, achievable only by moving onto filled cells, is equal to the Manhattan distance between them.

The Manhattan distance between two cells $(a, b)$ and $(c, d)$ is equal to $|a - c| + |b - d|$.

Find a way to add filled cells that satisfies these conditions and minimizes the total number of filled cells.

给你一个 $n \times m$ 的网格。其中一些格子已被填充，另一些为空。

一座“城市”是指一个极大的（按包含关系）已填充格子集合，使得该集合中任意两个格子之间都可通过仅在该集合内、沿边相邻（即上下左右）移动而互相到达。换言之，一座城市就是由相邻（上下左右）格子连边所构成的已填充格子的连通分量。

初始时，网格上恰好存在两座城市。你需要将若干空格子改为已填充格子，使得以下两个条件同时满足：

• 最终网格上仅存在一座城市；
• 任意两个已填充格子之间的最短路径（该路径只能经过已填充格子）的长度等于它们之间的曼哈顿距离。

格子 $(a, b)$ 与 $(c, d)$ 之间的曼哈顿距离定义为 $|a - c| + |b - d|$。

请找出一种添加已填充格子的方案，在满足上述条件的前提下，使最终已填充格子的总数最小。

Input consists of multiple test cases. The first line contains a single integer $t$, the number of test cases ($1 \le t \le 5000$).

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 50$, $nm \geq 3$).

The next $n$ lines describe the grid. The $i$-th line contains a string $s_i$ of length $m$. $s_{i,j}$ is '#' if the cell in position $(i, j)$ is filled, and '.' if it is empty.

It is guaranteed that there are exactly two cities in the initial grid.

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $25\,000$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output $n$ lines, each containing a string of length $m$, describing the grid you create in the same format as the input.

If there are multiple possible answers with the minimum number of filled cells print any.

对于每个测试用例，输出 $n$ 行，每行包含一个长度为 $m$ 的字符串，以与输入相同的格式描述你构造的网格。

如果存在多个满足最少填充值单元格数的可行答案，输出任意一个即可。

In the first test case, we can add a single filled cell between the two cities to connect them. We can verify that the second condition is satisfied.

In the second test case, we can also connect the cities with a single filled cell, while satisfying the second condition.

In the third test case, note that if we filled the 3 cells in the top left, the cities would be connected, but the second condition would not be satisfied for cells $(4, 2)$ and $(2, 4)$.

在第一个测试用例中，我们可以在两座城市之间添加一个填充单元格以将它们连接起来。我们可以验证第二个条件得到满足。

在第二个测试用例中，我们同样可以通过一个填充单元格连接这两座城市，同时满足第二个条件。

在第三个测试用例中，请注意：如果我们填充左上角的 3 个单元格，则这两座城市将被连接，但单元格 $(4, 2)$ 和 $(2, 4)$ 不满足第二个条件。