Вам дана таблица \(n \times m\). Некоторые клетки заполнены, некоторые пустые.
Город — это максимальное (по включению) множество заполненных клеток, такое что можно дойти из любой клетки города до любой другой клетки города, перемещаясь в соседние по стороне клетки, только по клеткам города. Другими словами, город — это компонента связности заполненных клеток, где ребро проводится между соседними по стороне заполненными клетками.
Изначально в таблице находятся два города. Вы хотите поменять некоторые пустые клетки на заполненные, так что выполняются два условия:
- В таблице находится один город.
- Кратчайший путь между любыми двумя заполненными клетками, если можно перемещаться только по заполненным клеткам, равно манхеттенскому расстоянию между клетками.
Манхеттенское расстояние между двумя клетками \((a, b)\) и \((c, d)\) равняется \(|a - c| + |b - d|\).
Найдите способ заполнить некоторые клетки, чтобы все условия выполнялись и общее количество заполненных клеток было минимально.
Выходные данные
Для каждого набора входных данных выведите \(n\) строк, каждая содержит строку длины \(m\) — описание таблицы, которую вы сделали в том же формате, что во входных данных.
Если существует несколько возможных способов заполнить некоторые пустые клетки, чтобы общее количество заполненных клеток было минимально, выведите любой.
Примечание
В первом наборе входных данных мы добавляем одну заполненную клетку между двумя городами, чтобы соединить их. Можно убедиться, что второе условие также выполняется.
Во втором наборе входных данных мы также соединяем города одной заполненной клеткой, также выполняя второе условие.
В третьем наборе входных данных, обратите внимание, что если мы заполним 3 клетки слева сверху, города будут соединены, однако второе условие не будет выполняться для пары клеток \((4, 2)\) и \((2, 4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
1 3
#.#
2 2
.#
#.
4 4
..##
...#
#...
##..
6 6
.##...
##....
......
....##
.....#
...###
6 5
.#..#
.#..#
.#..#
.#.##
.#...
##...
5 5
#####
#...#
#.#.#
#...#
#####
4 4
.##.
##.#
#.##
.##.
5 5
..###
....#
.....
#....
#....
5 6
.##...
##....
#....#
....##
...##.
6 5
..##.
...##
....#
#....
##...
.##..
5 4
..##
..#.
..#.
#...
#...
|
###
.#
##
..##
..##
###.
##..
.##...
###...
..#...
..####
...###
...###
.####
.####
.####
.####
.#...
##...
#####
#####
#####
#####
#####
.##.
####
####
.##.
..###
..###
..#..
###..
#....
.##...
###...
######
...###
...##.
..##.
..###
..###
###..
###..
.##..
..##
..#.
..#.
###.
#...
|