Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача Y. Робинзон и крокодилы (пробный тур регионального этапа)

Автор задачи: Всероссийская олимпиада школьников по программированию

Первоисточник: Пробный тур регионального этапа

URL первоисточника: http://neerc.ifmo.ru/school/spb/regional-2015-practice.zip

Задачу добавил: alef

Успешно сдано решений: 99

Имя входного файла: input.txt
Имя выходного файла: output.txt

Время на тест: 2 с
Ограничения по памяти: 256 Мб

Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.

На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.

В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.

Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.

Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.

Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.

Формат входного файла

В первой строке входного файла записаны числа n и m — размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» — север, «S» — юг, «E» — восток, «W» — запад.

Формат выходного файла

Выходной файл должен содержать одно число — максимальное количество крокодилов, которых можно прогнать, не разозлив.

Пример входного файла - 1
1 5
WN.SE


Пример выходного файла - 1
4

Пример входного файла - 2
1 3
E.W


Пример выходного файла - 2
0

Пример входного файла - 3
3 4
.N.W
WWSS
EWEW


Пример выходного файла - 3
4

Пояснение к примеру

Рисунок показывает исходное расположение крокодилов в третьем примере.

Система оценки и описание подзадач

Данная задача содержит три подзадачи. Баллы за подзадачу начисляются только в том случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1 (30 баллов)

1 ≤ n, m ≤ 30

Подзадача 2 (30 баллов)

1 ≤ n, m ≤ 500

Подзадача 3 (40 баллов)

1 ≤ n, m ≤ 2000

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.








 

Сдать задачу

Задать вопрос жюри по этой задаче