34624번 - 제식 훈련 2

제식 훈련을 위해 연병장에 총 $N \times M$명의 훈련병이 오와 열을 맞추어 $N$행 $M$열로 배치되어 있다. $(i, j)$는 $i$행 $j$열의 위치를 의미한다 ($1 \leq i \leq N, 1 \leq j \leq M$). 각 훈련병은 동(E), 서(W), 남(S), 북(N) 네 방향 중 하나를 바라보고 있다.

이제 모든 훈련병이 동시에 자신이 바라보는 방향으로 이동하는 훈련을 진행하려고 한다. 이때 훈련병 간의 충돌을 방지하기 위해, 다음 조건들을 반드시 만족해야 한다.

모든 훈련병 $(i, j)$에 대해,

• $(i, j)$의 훈련병이 동쪽(E)을 바라본다면, $j < k \leq M$를 만족하는 모든 정수 $k$에 대해 $(i, k)$의 훈련병 또한 동쪽(E)을 바라보아야 한다.
• $(i, j)$의 훈련병이 서쪽(W)을 바라본다면, $1 \leq k < j$를 만족하는 모든 정수 $k$에 대해 $(i, k)$의 훈련병 또한 서쪽(W)을 바라보아야 한다.
• $(i, j)$의 훈련병이 남쪽(S)을 바라본다면, $i < k \leq N$를 만족하는 모든 정수 $k$에 대해 $(k, j)$의 훈련병 또한 남쪽(S)을 바라보아야 한다.
• $(i, j)$의 훈련병이 북쪽(N)을 바라본다면, $1 \leq k < i$를 만족하는 모든 정수 $k$에 대해 $(k, j)$의 훈련병 또한 북쪽(N)을 바라보아야 한다.

현재 훈련병들의 방향 배치가 주어졌을 때, 조건을 만족시키기 위해 방향을 변경해야 하는 훈련병 수의 최솟값을 구하여라.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \leq N, M \leq 2,000$)

다음 $N$개의 줄에 걸쳐 각 행의 훈련병들이 바라보는 방향을 나타내는 $M$개의 문자가 공백 없이 주어진다. 이때 주어지는 문자는 E, W, S, N 중 하나이며, 각각 동쪽, 서쪽, 남쪽, 북쪽을 뜻한다.

첫째 줄에 조건을 만족시키기 위해 방향을 바꿔야 하는 훈련병 수의 최솟값을 출력한다.