ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Захоронения в океане

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Посреди безбрежного океана расположился Архипелаг. Издревле на островах Архипелага жило племя людоедов. С давних пор Шаманы племени общались с богами и направляли племя на его жизненном пути, вызывали дожди во время засухи и солнце в сезон дождей. Давным-давно главный Шаман племени, находясь в священном трансе, прыгнул в одно из морей и утонул, указав тем самым Священное Море. С тех пор вся земля внутри этого моря считается священной. Каждого умершего Шамана, по древнему закону, положено хоронить на священной земле. Но души умерших шаманов не могут ужиться друг с другом, поэтому каждого шамана хоронят на отдельном острове. Древнее предсказание гласит, что как только двух шаманов похоронят на одном острове, наступят страшные времена, и племя погибнет.
Сколько же поколений Шаманов сможет пережить племя? Этот вопрос не давал покоя каждому вождю, приходившему к власти. И вот один вождь приказал составить карту Архипелага. Целый год трудились людоеды и составили эту карту, но карта оказалась слишком большой и сложной, чтобы можно было посчитать священные острова. Тогда главный Шаман обратился к богам с просьбой – помочь сосчитать острова. Боги откликнулись на его призыв, и вот, в огне и свете, на землю спустились Программист и Компьютер (как вы наверно догадались, этот Программист – именно вы). Помогите же племени сосчитать острова, и боги вернут вас назад. Но помните, что внутри островов есть моря, внутри них – еще острова и т.д.

Исходные данные

На входе в первой строке находятся четыре целых числа W, H, X, Y, разделенные одним или несколькими пробелами. 1 ≤ W, H ≤ 500 – это ширина и высота карты, соответственно. 1 ≤ XW и 1 ≤ YH – координаты точки, где утонул древний Шаман. В следующих H строках находится описание карты. Каждая строка содержит W символов, описывающих карту. Символ "." обозначает фрагмент моря, а символ "#" – фрагмент острова. Фрагменты считаются принадлежащими одному морю, если они лежат рядом по горизонтали, по вертикали или по диагонали. Фрагменты считаются принадлежащими одному острову, если они лежат рядом по горизонтали или по вертикали (но не по диагонали). Координаты отсчитываются от левого верхнего угла. Острова, касающиеся границы карты, не могут быть использованы для захоронений шаманов – шаманы этого очень не любят.

Результат

Необходимо вывести единственное целое число – количество островов, пригодных для захоронения шаманов.

Примеры

исходные данныерезультат
9 7 1 1
........#
.#######.
.#.....#.
.#.#.#.#.
.#.....#.
.#######.
#........
3
9 7 3 3
........#
.#######.
.#.....#.
.#.#.#.#.
.#.....#.
.#######.
#........
2
Автор задачи: Станислав Скорб (подготовил - Иван Дашкевич)
Источник задачи: Open collegiate programming contest for student teams, Ural State University, March 15, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1250. Захоронения в океане