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

Задача Y - 2017. Робинзон и крокодилы

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

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

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

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

512 мегабайт

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

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

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

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

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

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

Формат входных данных

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

Формат выходных данных

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

Примеры входных и выходных данных

входные данные

выходные данные

1 5

WN.SE

4

1 3

E.W

0

3 4

.N.W

WWSS

EWEW

4


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

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


Описание подзадач и системы оценивания

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

Подзадача

Баллы

Дополнительные ограничения

Необходимые подзадачи

Информация о проверке

n, m

1

30

1 ≤ n, m ≤ 30


полная

2

30

1 ≤ n, m 500

1

полная

3

40

1 ≤ n, m 2000

1, 2

полная

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

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

Сдать задачу

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