City Union
Contest: Codeforces Round 854 by cybercats (Div. 1 + Div. 2)
Difficulty rating: 2300
Tags: constructive algorithms, dfs and similar, dsu, geometry, greedy, implementation, math

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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)$$$.

Example input:
11
1 3
#.#
2 2
.#
#.
4 4
..##
...#
#...
##..
6 6
.##...
##....
......
....##
.....#
...###
6 5
.#..#
.#..#
.#..#
.#.##
.#...
##...
5 5
#####
#...#
#.#.#
#...#
#####
4 4
.##.
##.#
#.##
.##.
5 5
..###
....#
.....
#....
#....
5 6
.##...
##....
#....#
....##
...##.
6 5
..##.
...##
....#
#....
##...
.##..
5 4
..##
..#.
..#.
#...
#...

Example output:
###

.#
##

..##
..##
###.
##..

.##...
###...
..#...
..####
...###
...###

.####
.####
.####
.####
.#...
##...

#####
#####
#####
#####
#####

.##.
####
####
.##.

..###
..###
..#..
###..
#....

.##...
###...
######
...###
...##.

..##.
..###
..###
###..
###..
.##..

..##
..#.
..#.
###.
#...

Editorial:
Let's note, that the resulting grid is correct if and only if filled cells form continious segment in each row and column (condition *) and there is one city.
So we can define a filling operation: given a grid, fill all cells between the most left and most right cells in each row and the most up and most down cells in each column. Doing this operation $$$(n+m)$$$ times we get that condition * is satisfied and we filled cells that definitely should be filled. If now there is one city, we solved the problem.
But if there are still two cities, their projections to horisontal and vertical axes do not intersect. So we need to connect them with some path.
Let's consider the case when one city is upper left than the other city (otherwise we can apply rotation and get this case). Let's define the lowest row of the first city as $$$i_1$$$, the right column of the first city as $$$j_1$$$, the upper row of the second city as $$$i_2$$$ and the left column of the second city as $$$j_2$$$. We can fill cells on any Manhattan shortest path between cells $$$(i_1, j_1)$$$, $$$(i_2, j_2)$$$. After that again using filling operation we will fill cells that should be filled.
It is easy to see, that by this solution we will get the smallest possible number of filled cells.
Time complexity: $$$O(nm (n + m))$$$.