Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2297. Оборона города
Задачи на идеюОлимпиадные задачи на русском языке
| 02/10/2016 | Личное первенство по спортивному программированию (F) |
| 14/07/2023 | Лето 2023-9 (командное) (H) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для обороны города от монголов Туонг Лу Ким должен построить стену таким образом,
чтобы все важные здания города (мэрия, школа и т.д.) находились внутри стены.
Стена должна быть связной (клетки, занятые стеной, должны иметь общую сторону) и иметь минимальную длину.
Если существует несколько вариантов размещения стены с минимальной длиной, то нужно выбрать вариант,
при котором все здания находятся внутри одной связной области, охватываемой стеной, и площадь этой области минимальна.
Если есть несколько вариантов с минимальной длиной стены и минимальной площадью, то мистера Кима устроит любой вариант.
Напишите программу, которая по плану городу найдет оптимальный способ строительства стены.
Первая строка ввода содержит два целых числа `N` и `M` (`3\ ≤\ N,\ M\ ≤\ 1000`). Следующие `N` строк содержат `M`
символов '*' (важные здания) и '.' (место, где можно строить стену). Гарантируется, что на
плане есть хотя бы один символ '*' и нет '*'на его границах.
Вывести `N` строк, содержащих `M` символов – план строительства стены. Клетки, где нужно построить стену, должны
быть помечены символом '#'.
Пример ввода
5 6 ...... .*.... ....*. ...... ......
Пример вывода
###### #*...# ####*# ...### ......
