Олимпиадный тренинг

Задача . Лесные пожары


Задача

Темы:
В период засухи существует опасность лесных пожаров. Чем раньше получится ликвидировать пожар, тем меньший вред он нанесет. Поэтому для предотвращения больших пожаров создана мобильная пожарная бригада. Для мониторинга ситуации проводится аэросъемка местности. Территория разбивается на квадратные участки (клетки), сторона каждой из которых равна 1 км. Клетки нумеруются по принципу: столбцы обозначаются буквами латинского алфавита, а строки — числами. Клетка может содержать лес или пустое пространство. Для ликвидации пожара высылается пожарная бригада, которую доставляют вертолетом максимально близко к точке возгорания. Но приземлиться в любой точке местности вертолет не может. Считается, что точка доступна для посадки, если она находится в центре квадрата из свободных клеток со стороной размера 5, расположенного целиком внутри территории. Необходимо найти количество подходящих под условие задачи точек посадки и расстояние до максимально близкой к точке возгорания клетки, в которую возможно совершить посадку. Если таких клеток найдено несколько, укажите клетку с лексикографически минимальным обозначением столбца и минимальным номером ряда.

Входные данные:
В первой строке входного файла 26.txt находится число N - количество клеток, занятых лесом (натуральное число, не превышающее 10 000).
Каждая из следующих N строк содержит латинскую букву из набора 26 различных букв — обозначение ряда и натуральное число, не превышающих 1000: номер клетки в этом ряду, занятой лесом.
В последней строке вводится латинская буква и натуральное число — координаты клетки, в которой произошло возгорание.

Выходные данные:
Два числа: количество подходящих под условие точек посадки и округленное до целого числа расстояние от ближайшей к точке возгорания точки посадки. Числа разделить пробелом.

Пример входного файла:
4
A 1
C 1
B 2
B 4
B 3
Если считать, что территория ограничена набором из 7 букв от А до G и 7 строк, то под условие посадки подойдут две клетки: Е 4 и Е 5.
Максимально близкая к точке возгорания клетка, доступная для посадки – это Е 4. Расстояние от Е4 до В3 3.16... Округленное до целого значения 3.
Ответ для примера: 2 3

Скачать файл

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя