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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:alligator.in   Ограничение памяти:256 Мб
Выходной файл:alligator.out  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Система оценивания

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

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

1 ≤ n, m ≤ 30

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

1 ≤ n, m ≤ 500

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

1 ≤ n, m ≤ 2000

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

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

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

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

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

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

Примеры тестов

Входной файл (alligator.in) Выходной файл (alligator.out)
1
1 5
WN.SE
4
2
1 3
E.W
0
3
3 4
.N.W
WWSS
EWEW
4

0.091s 0.009s 15