Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
915. Секретный бункер
Поиск в глубину (DFS)Бинарный поиск
Олимпиадные задачи на русском языке
| 11/12/2005 | Районно-городские командные соревнования (4) |
| 10/03/2015 | Занятие 16 (C) |
| 25/11/2023 | Марафон 80 задач, 6 этап (J) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Имеется план секретного бункера в виде прямоугольного поля, на котором местоположение бомб отмечено символом '*', секретных объектов – символом '?', а пустые клетки – символом '.'. В случае опасности подрыв любой бомбы должен приводить к уничтожению секретных объектов. Бомба при взрыве уничтожает все объекты, для которых расстояние от центра клетки с бомбой до центра клетки с объектом меньше или равно `D`. Если в пределах действия бомбы оказывается другая бомба, она также взрывается.
Напишите программу, вычисляющую минимальное значение `D`, при котором взрыв любой бомбы приводит к уничтожению всех секретных объектов.
Во входном файле несколько тестов. В первом строке каждого теста содержатся два целых числа `N` и `M` через пробел – размеры плана бункера (`1\ ≤\ N\ ≤\ 50`, `1\ ≤\ M\ ≤\ 50`). Далее следует `N` строк, содержащих по `M` символов '.', '*' и '?'. План содержит от 1 до 100 символов '?' и от 1 до 100 символов '*'. Строка, содержащая "0 0", сигнализирует о завершении набора тестов и не обрабатывается.
В выходной файл для каждого теста вывести строку, содержащую одно вещественное число – минимальное значение D для соответствующего плана с точностью `10^{-6}`.
Пример ввода
2 3 *.* .?. 5 5 ***** .?.?. ..?.. .?.?. ***** 0 0
Вывод для примера
1.414214 3.000000
