City Union

1000ms

262144K

Description:

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:

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:

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.

Sample Input:

11
1 3
#.#
2 2
.#
#.
4 4
..##
...#
#...
##..
6 6
.##...
##....
......
....##
.....#
...###
6 5
.#..#
.#..#
.#..#
.#.##
.#...
##...
5 5
#####
#...#
#.#.#
#...#
#####
4 4
.##.
##.#
#.##
.##.
5 5
..###
....#
.....
#....
#....
5 6
.##...
##....
#....#
....##
...##.
6 5
..##.
...##
....#
#....
##...
.##..
5 4
..##
..#.
..#.
#...
#...

Sample Output:

###

.#
##

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

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

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

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

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

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

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

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

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

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

Informação

Provedor Codeforces

Código CF1799E