CF1799E City Union

给定一个 $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$。$s_{i,j}$ 为 '\#' 表示该位置为填充格子，为 '.' 表示该位置为空格子。 保证初始网格上恰好有两个城市。 保证所有测试数据中 $n \cdot m$ 的总和不超过 $25\,000$。

对于每组测试数据，输出 $n$ 行，每行一个长度为 $m$ 的字符串，描述你构造的网格，格式与输入相同。 如果有多种填充格子数最少的方案，输出任意一种均可。

在第一个测试样例中，我们可以在两个城市之间添加一个填充格子将它们连接起来，可以验证第二个条件也满足。 在第二个测试样例中，同样可以用一个填充格子连接两个城市，同时满足第二个条件。 在第三个测试样例中，注意如果我们填充左上角的 3 个格子，虽然城市连通了，但对于格子 $(4, 2)$ 和 $(2, 4)$，第二个条件不满足。 由 ChatGPT 4.1 翻译