21516번 - Робинзон и крокодилы 다국어

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

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

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

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

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

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

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

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

• $1 \le n,m \le 2000$

Рисунок к третьему примеру: