Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1452. Торанианхендж
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание ( 8G) |
| 09/07/2010 | Лето 2010 - 8 (G) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
...... .#...# ...... .#....
