printРабочее место участника

printЗадачи

1452. Торанианхендж

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Планетарное Правительство торанианцев приняло решение о постройке масштабного комплекса скульптур в свою честь. Для этого на карте планеты был выделен прямоугольный участок, поверхность которого можно представить в виде таблицы `W\ times\ H` клеток, ориентированных вдоль сторон света.
Каждая клетка рассматриваемого участка может быть свободна для застройки и обозначаться символом '.' (ASCII 46), либо быть занята обелиском знаменитому торанианцу. Обелиски торанианцев строго симметричны либо вдоль направления восток-запад, либо вдоль направления север-юг, либо в обоих направлениях одновременно и обозначаются на карте как '|' (ASCII 124), '-' (ASCII 45) и '+' (ASCII 43) соответственно.
Каждая скульптура комплекса занимает одну клетку. Из эстетических соображений было решено, что расположение скульптур должно обеспечить выполнение следующих условий.
  • Cкульптуры, находящиеся в той же строке карты, что и любой обелиск, симметричный в направлении восток-запад, расположены симметрично относительно него.
  • Cкульптуры, находящиеся в том же столбце карты, что и любой обелиск, симметричный в направлении север-юг, расположены симметрично относительно него.
  • Для каждого обелиска, симметричного в направлении восток-запад, имеется хотя бы одна скульптура, находящаяся в той же строке.
  • Для каждого обелиска, симметричного в направлении север-юг, имеется хотя бы одна скульптура, находящаяся в том же столбце.
Для выполнения последних двух условий разрешено даже устанавливать скульптуру на той же клетке, что и существующий обелиск.
Требуется по данной карте участка составить план расположения скульптур или определить, что это невозможно.
Формат входного файла
В первой строке входного файла находятся числа `W` и `H`. В следующих `H` строках по `W` символов находится описание карты.
Формат выходного файла
Выходной файл должен содержать `H` строк по `W` символов в каждой – искомый план сооружения. При этом `J`-й символ `I`-й строки должен быть символом '#' (ASCII 35), если в данную клетку следует установить скульптуру, и '.' (ASCII 46) – в противном случае. Если решений несколько, выведите любое из них.
Если составить план невозможно, выходной файл должен содержать единственную строку NONE.
Ограничения
`1\ ≤\ W,\ H\ ≤\ 100`.
Поле содержит не менее одного и не более 100 обелисков.

Пример ввода 1

3 2
.|.
-..

Пример вывода 1

.#.
#..

Пример ввода 2

3 2
.||
-..

Пример вывода 2

NONE

Пример ввода 3

6 4
......
...|..
.-....
......

Пример вывода 3

......
.#...#
......
.#....
Источник: Отборочные соревнования ВКОШП Дальневосточного региона, 2008
loading