Робинзон и крокодилы

시간 제한2초메모리 제한1024 MB

요약

격자 위의 악어들은 각자 정해진 방향으로 도망친다. 충돌 없이 하나씩 쫓아낼 수 있는 악어의 최대 수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 위상 정렬, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

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

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

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

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

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

입력

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

출력

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

제한

$1 \le n,m \le 2000$

힌트

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

예제3

예제 1
입력
```
1 5
WN.SE
```
예상 출력
```
4
```
예제 2
입력
```
1 3
E.W
```
예상 출력
```
0
```
예제 3
입력
```
3 4
.N.W
WWSS
EWEW
```
예상 출력
```
4
```