Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2043. Строительство дамбы
Поиск в ширину (BFS)Максимальный поток
Олимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (F) |
| 23/04/2014 | Занятие 22 (F) |
| 18/07/2016 | Лето 2016 - 10 (командная) (E) |
| 03/07/2019 | Лето 2019 - 2 (D) |
| 05/07/2023 | Лето 2023-5 простые (E) |
| 03/07/2024 | Лето 2024-5 простые (E) |
| 04/12/2024 | ЦОП1 (дорешивание) Графы 2 (проводит BOGAT) (F) |
| 09/07/2025 | Лето 2025-5 (E) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для защиты столицы Бинарии от наводнений в ущелье между морем и городом необходимо построить дамбу.
Чтобы уменьшить расходы на строительство, как часть дамбы можно использовать скалы, расположенные между
городом и морем.
Напишите программу, которая для заданного расположения скал определит план размещения остальных
частей дамбы, при котором дамба будет полностью защищать город от наводнений, и
потребуются минимальные расходы на строительство. Вода не может протечь между клетками, занятые дамбой
или скалами и соприкасающиеся сторонами, но может протечь между такими клетками, соприкасающиеся только углами.
Формат ввода
Первая строка ввода содержит два целых числа `N` и `M` (`5\ ≤\ N,\ M\ ≤\ 25`) – размеры карты местности.
Далее следует `N` строк, содержащих по `M` символов. Символ '.' означает свободную клетку, а
символ '*' – клетку, занятую скалой. Море находится на верхней границе карты, а город — на нижней.
На левой и правой границе карты находятся горы.
Формат вывода
Вывести `N` строк, содержащих по `M` символов — карту местности, на которой символом '#' отмечены
места строительства дополнительных частей дамбы. Можно вывести любой из минимизирующих строительство вариантов.
Пример ввода
5 6 *..... ...... **.*.. *..**. ......
Пример вывода
*..... ...... **#*.. *..**# ......
