B 787

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define watch(x) cout << (#x) << " : " << x << '\n'

using namespace std;

const int N = 2e3 + 128;
char a[N][N];
int n, m;

inline int decode(char x) {
    switch (x) {
    case 'W':
        return 0;
    case 'E':
        return 1;
    case 'N':
        return 2;
    case 'S':
        return 3;
    }
    return -1;
}

bool escaped[N][N];
pair<int, int> closest[N][N][4];

bool can_delete(int i, int j) {
    if (escaped[i][j])
        return false;
    auto [ci, cj] = closest[i][j][decode(a[i][j])];
    return ci == -1 || cj == -1;
}

void push_next(int i, int j, int a, int b) {
    if (closest[i][j][a].first == -1 || closest[i][j][a].second == -1)
        return;
    closest[closest[i][j][a].first][closest[i][j][a].second][b] = closest[i][j][b];
}

int ans = 0;

void apply_delete(int i, int j) {
    if (escaped[i][j])
        return;
    ans++;
    escaped[i][j] = true;
    push_next(i, j, 0, 1);
    push_next(i, j, 1, 0);
    push_next(i, j, 2, 3);
    push_next(i, j, 3, 2);
}

vector < pair<int, int> > find_nearest(int i, int j) {
    vector < pair<int, int> > res;
    for (int d = 0; d < 4; d++) {
        auto [ci, cj] = closest[i][j][d];
        if (ci != -1 && cj != -1)
            res.push_back({ ci, cj });
    }
    return res;
}

bool was[N][N];

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int i = 1; i <= n; i++) {
        int prev = -1;
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '.')
                continue;
            closest[i][j][0] = { i, prev };
            prev = j;
        }
        prev = -1;
        for (int j = m; j >= 1; j--) {
            if (a[i][j] == '.')
                continue;
            closest[i][j][1] = { i, prev };
            prev = j;
        }
    }

    for (int j = 1; j <= m; j++) {
        int prev = -1;
        for (int i = 1; i <= n; i++) {
            if (a[i][j] == '.')
                continue;
            closest[i][j][2] = { prev, j };
            prev = i;
        }
        prev = -1;
        for (int i = n; i >= 1; i--) {
            if (a[i][j] == '.')
                continue;
            closest[i][j][3] = { prev, j };
            prev = i;
        }
    }

    vector < pair<int, int> > can;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] != '.' && can_delete(i, j))
                was[i][j] = true, can.push_back({ i, j });

    while (!can.empty()) {
        for (auto [i, j] : can)
            apply_delete(i, j);
        vector < pair<int, int> > nxt;
        for (auto [i, j] : can)
            for (auto [x, y] : find_nearest(i, j))
                if (!was[x][y] && can_delete(x, y))
                   was[x][y] = true, nxt.push_back({ x, y });
        can = nxt;
    }

    cout << ans << '\n';
}

int32_t main() {
    boost;
    solve();
    return 0;
}