images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
25/04/2024 03:09:10

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

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1310. Защита страны

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

Королевство Флатландия имеет форму прямоугольника размером `N`x`M` клеток. Для защиты Флатландия в нескольких клетках были построены крепости, в которых размещены войска. При нападении войско из крепостей пешим маршем отправляется к месту появления врага. Войско может переходить только в соседнюю клетку, имеющую общую границу с клеткой, где находится войско. Такой переход выполняется за 1 единицу времени. Некоторые клетки Флатландии, в которых находятся леса и озера, горы и равнины, являются непроходимыми для войск. Король хочет выяснить за какое минимальное время войска могут гарантированно добраться до остальных клеток страны.
Напишите программу, которая вычисляет это время для заданной карты Флатландии.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N\ ≤\ 200`, `1\ ≤\ M\ ≤\ 200`) – размеры Флатландии. Далее следует `N` строк, содержащих по `M` символов '#' (непроходимая для войск клетка), '.' (удобная для передвижения войск клетка) и '*' (клетка с крепостью). Гарантируется, что войска могут добраться до всех клеток, обозначенных символом '.', из какой-либо крепости.
Вывести одно целое число – минимальное время для достижения войсками любой клетки страны, обозначенной символом '.'.

Пример ввода

4 4
*#..
...*
.##.
...#

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

5
loading