City Union (Codeforces 1799E)
Tags: Greedy, geometry

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.

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

Sample Inputs:
11
1 3
#.#
2 2
.#
#.
4 4
..##
...#
#...
##..
6 6
.##...
##....
......
....##
.....#
...###
6 5
.#..#
.#..#
.#..#
.#.##
.#...
##...
5 5
#####
#...#
#.#.#
#...#
#####
4 4
.##.
##.#
#.##
.##.
5 5
..###
....#
.....
#....
#....
5 6
.##...
##....
#....#
....##
...##.
6 5
..##.
...##
....#
#....
##...
.##..
5 4
..##
..#.
..#.
#...
#...

Sample Outputs:
###

.#
##

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

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

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

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

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

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

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

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

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

Solution (Python):
""""""

def initialize_solution():
    ...

def convexify(grid):
    row = len(grid)
    col = len(grid[0])
    changed = True
    while changed:
        changed = False
        for r in range(row):
            left = -1
            right = -1
            for c in range(col):
                if grid[r][c] == '#':
                    if left == -1:
                        left = c
                    right = c
            for c in range(left, right):
                if grid[r][c] == '.':
                    grid[r][c] = '#'
                    changed = True
        for c in range(col):
            top = -1
            bot = -1
            for r in range(row):
                if grid[r][c] == '#':
                    if top == -1:
                        top = r
                    bot = r
            for r in range(top, bot):
                if grid[r][c] == '.':
                    grid[r][c] = '#'
                    changed = True
    return grid

def main():
    (row, col) = read()
    grid = [['.'] * (col + 2)] + [['.'] + list(read(str, False)) + ['.'] for _ in range(row)] + [['.'] * (col + 2)]
    convexify(grid)
    city = [[0] * (col + 2) for _ in range(row + 2)]
    citycount = 0
    cityborders = []
    for r in range(1, row + 1):
        for c in range(1, col + 1):
            if grid[r][c] == '#' and city[r][c] == 0:
                citycount += 1
                top = r
                left = c
                right = c
                bot = r
                stack = [(r, c)]
                while stack:
                    (rn, cn) = stack.pop()
                    if grid[rn][cn] == '.' or city[rn][cn] != 0:
                        continue
                    city[rn][cn] = citycount
                    if left > cn:
                        left = cn
                    if right < cn:
                        right = cn
                    if bot < rn:
                        bot = rn
                    for (dx, dy) in [(0, -1), (0, 1), (1, 0)]:
                        stack.append((rn + dx, cn + dy))
                cityborders.append((top, left, right, bot))
    if citycount == 1:
        write(*(''.join(grid[r][1:-1]) for r in range(1, row + 1)), sep='\n', end='\n\n')
        return
    assert cityborders[0][3] < cityborders[1][0]
    if cityborders[0][2] < cityborders[1][1]:
        grid[cityborders[0][3]][cityborders[1][1]] = '#'
    elif cityborders[0][1] > cityborders[1][2]:
        grid[cityborders[0][3]][cityborders[1][2]] = '#'
    else:
        assert False
    convexify(grid)
    write(*(''.join(grid[r][1:-1]) for r in range(1, row + 1)), sep='\n', end='\n\n')
    return
READ_FROM_FILE = None
OUTPUT_PREFIX = ''
INTERACTIVE = False
INTERACTIVE_WRONG_ANSWER = ''
import sys

def read(callback=int, split=True):
    if READ_FROM_FILE:
        ipt = sfile.readline().strip()
    else:
        ipt = input().strip()
    if INTERACTIVE and ipt == INTERACTIVE_WRONG_ANSWER:
        sys.exit()
    if split:
        return list(map(callback, ipt.split()))
    else:
        return callback(ipt)

def write(*objects, sep=' ', end='\n'):
    print(*objects, sep=sep, end=end, file=tfile, flush=True)

def solve_testcase():
    result = main()
    if result is not None:
        write(result)
sfile = None
tfile = None
if READ_FROM_FILE:
    sfile = open(READ_FROM_FILE + '.in', 'r')
    sfile.seek(0)
    tfile = open(READ_FROM_FILE + '.out', 'w')
if OUTPUT_PREFIX is None:
    OUTPUT_PREFIX = ''
    TOTAL_CASES = 1
else:
    initialize_solution()
    (TOTAL_CASES,) = read()
for CASE_NUMBER in range(1, TOTAL_CASES + 1):
    write(OUTPUT_PREFIX.replace('%d', str(CASE_NUMBER)), end='')
    solve_testcase()
if sfile is not None:
    sfile.close()
if tfile is not None:
    tfile.close()
READ_FROM_FILE = ''

Solution (Python):
import sys, io, os
try:
    Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
    Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())

def solve(n, m, a):
    lx = [-1] * n
    hx = [-1] * n
    ly = [-1] * m
    hy = [-1] * m
    for i in range(n):
        for j in range(m):
            if a[i][j]:
                if lx[i] == -1:
                    lx[i] = j
                hx[i] = j
                if ly[j] == -1:
                    ly[j] = i
                hy[j] = i
    cl = ch = -1
    for i in range(n):
        if lx[i] != -1:
            if cl == -1:
                cl = lx[i]
                ch = hx[i]
            else:
                if hx[i] > ch:
                    if lx[i] > ch:
                        lx[i] = ch
                    ch = hx[i]
                if lx[i] < cl:
                    if hx[i] < cl:
                        hx[i] = cl
                    cl = lx[i]
    for _ in range(2):
        for i in range(n):
            if lx[i] != -1:
                for j in range(lx[i], hx[i] + 1):
                    a[i][j] = 1
                    if ly[j] == -1 or ly[j] > i:
                        ly[j] = i
                    if hy[j] < i:
                        hy[j] = i
        for j in range(m):
            if ly[j] != -1:
                for i in range(ly[j], hy[j] + 1):
                    a[i][j] = 1
                    if lx[i] == -1 or lx[i] > j:
                        lx[i] = j
                    if hx[i] < j:
                        hx[i] = j
    return a
O = []
for _ in range(*Y()):
    (n, m) = Y()
    a = [[0] * m for i in range(n)]
    for i in range(n):
        s = Z().strip()
        for j in range(m):
            a[i][j] = s[j] == 35
    a = solve(n, m, a)
    for i in range(n):
        O.append(''.join(('.#'[a[i][j]] for j in range(m))))
    O.append('')
print('\n'.join(O[:-1]))

Solution (Python):
import sys, io, os
try:
    Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
    Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())

def disp(a):
    E = []
    for i in range(n):
        E.append(''.join(('.#'[a[i][j]] for j in range(m))))
    E.append('')
    print('\n'.join(E))

def solve(n, m, a):
    lx = [-1] * n
    hx = [-1] * n
    ly = [-1] * m
    hy = [-1] * m
    for i in range(n):
        for j in range(m):
            if a[i][j]:
                if lx[i] == -1:
                    lx[i] = j
                hx[i] = j
                if ly[j] == -1:
                    ly[j] = i
                hy[j] = i
    cl = ch = -1
    for i in range(n):
        if lx[i] != -1:
            if cl == -1:
                cl = lx[i]
                ch = hx[i]
            else:
                if hx[i] > ch:
                    if lx[i] > ch:
                        lx[i] = ch
                    ch = hx[i]
                if lx[i] < cl:
                    if hx[i] < cl:
                        hx[i] = cl
                    cl = lx[i]
    for _ in range(2):
        for i in range(n):
            if lx[i] != -1:
                for j in range(lx[i], hx[i] + 1):
                    a[i][j] = 1
                    if ly[j] == -1 or ly[j] > i:
                        ly[j] = i
                    if hy[j] < i:
                        hy[j] = i
        for j in range(m):
            if ly[j] != -1:
                for i in range(ly[j], hy[j] + 1):
                    a[i][j] = 1
                    if lx[i] == -1 or lx[i] > j:
                        lx[i] = j
                    if hx[i] < j:
                        hx[i] = j
    return a
O = []
for _ in range(*Y()):
    (n, m) = Y()
    a = [[0] * m for i in range(n)]
    for i in range(n):
        s = Z().strip()
        for j in range(m):
            a[i][j] = s[j] == 35
    a = solve(n, m, a)
    for i in range(n):
        O.append(''.join(('.#'[a[i][j]] for j in range(m))))
    O.append('')
print('\n'.join(O[:-1]))