Подразделы

Другие разделы

Дата и время

06/03/2025 20:11:48

Авторизация

Районно-городские командные соревнования

1. Парковка 2. Кроссворд 3. Новый компилятор 4. Секретный бункер 5. Минимизация шаблона 6. Палочки 7. Тосты 8. Угадай число

4. Секретный бункер

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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