Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Борьба с сорняками
Будущий фермер Дмитрий получил в наследство от отца участок размером N на M квадратов. Каждый квадрат представляет собой либо чистую землю, либо камень, который настолько велик, что его никак нельзя убрать с квадрата. Последним наказом отца было пожелание того, чтобы Дмитрий не начинал работы с землей до тех пор, пока она полностью не зарастет сорняком. При этом отец сообщил сыну, в каком именно квадрате находится сорняк и каким образом он размножается. Итак, изначально сорняк находится в клетке с номером Mx по горизонтали и номером My по вертикали. Будем считать, что левый нижний квадрат участка имеет координаты (1, 1), а правый верхний (M, N). Сорняк за одну неделю успевает разрастись на все соседние квадраты (2 вертикальные, 2 горизонтальные и 4 диагональные) при условии, что эти квадраты не заняты камнями или другим сорняком. Проиллюстрируем историю зарастания участка примером (участок имеет размеры 3 и 4, ‘.’ обозначается чистая земля, ‘*’ – квадрат с камнем, ‘M’ – сорняк, который изначально находится в клетке (1,1)):
....
..*.
M**.

....
MM*.
M**.

MMM.
MM*.
M**.
MMMM
MM*M
M**.

MMMM
MM*M
M**M

Начальное
состояние участка
 1 неделя 2 неделя 3 неделя 4 неделя


Дмитрий хочет узнать по плану участка и координате клетки с сорняком, сколько недель ему необходимо ждать момента, когда он может начать засеивать свой новый участок.
Входные данные:
В первой строке входного файла расположено 4 целых числа M, N, Mx, My (1 ≤ M, N, Mx, My ≤ 100). 

 Далее следует N строк по M символов в каждой. В каждой из этих строк могут быть расположены следующие символы: ‘.’ , ‘*’ (без кавычек).
Выходные данные:
В выходной файл требуется вывести единственное число – количество недель, которое предстоит ждать Дмитрию.

Примеры:
input.txt output.txt
1 4 3 1 1
....
..*.
.**.
4

Сложность задачи: 25%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 20, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]