Crocks

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

vector< string > field;
// true if can out
vector< vector< bool > > vup, vdown, vleft, vright;
queue< pair<int, int> > out;
int n, m;

void solve()
{
  int ans = 0;
  while( out.size() > 0 )
  {
    pair<int, int> crock = out.front();
    int ci = crock.F, cj = crock.S;
    char dir = field[ci][cj];
    out.pop();
    if (dir == '.') continue;
    ans++;
    field[ci][cj] = '.';
    if (dir != 'N' && vdown[ci+1][cj]) // vdown
    {
      vdown[ci][cj] = true;
      for(int i=ci-1; i>=0; --i)
        if (field[i][cj] == '.')
          vdown[i][cj] = true;
        else if (field[i][cj] == 'S')
        {
          vdown[i][cj] = true;
          out.push({i, cj});
          break;
        }
        else
          break;
    }
    if (dir != 'S' && vup[ci-1][cj]) // vup
    {
      vup[ci][cj] = true;
      for(int i=ci+1; i<n+2; ++i)
        if (field[i][cj] == '.')
          vup[i][cj] = true;
        else if (field[i][cj] == 'N')
        {
          vup[i][cj] = true;
          out.push({i, cj});
          break;
        }
        else
          break;
    }
    if (dir != 'W' && vright[ci][cj+1]) // vright
    {
      vright[ci][cj] = true;
      for(int j=cj-1; j>=0; --j)
        if (field[ci][j] == '.')
          vright[ci][j] = true;
        else if(field[ci][j] == 'E')
        {
          vright[ci][j] = true;
          out.push({ci, j});
          break;
        }
        else
          break;
    }
    if (dir != 'E' && vleft[ci][cj-1]) // vleft
    {
      vleft[ci][cj] = true;
      for(int j=cj+1; j<m+2; ++j)
        if (field[ci][j] == '.')
          vleft[ci][j] = true;
        else if(field[ci][j] == 'W')
        {
          vleft[ci][j] = true;
          out.push({ci, j});
          break;
        }
        else
          break;
    }
  }
  cout << ans;
}

void read_data()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  #ifdef AZHUKOV
  freopen("input.txt", "r", stdin);
  #endif // AZHUKOV

  cin >> n >> m;
  field.resize( n + 2, string(m+2, '.') );
  for(int i=1; i<=n; ++i)
    for(int j=1; j<=m; ++j)
      cin >> field[i][j];

  vup.resize( n + 2, vector<bool>(m+2, false) );
  for(int j=0; j<m+2; ++j)
  {
    vup[0][j] = true;
    for(int i=1; i<n+2; ++i)
      if (field[i][j] == '.')
        vup[i][j] = true;
      else if (field[i][j] == 'N')
      {
        vup[i][j] = true;
        out.push({i, j});
        break;
      }
      else
        break;
  }

  vdown.resize( n + 2, vector<bool>(m+2, false) );
  for(int j=0; j<m+2; ++j)
  {
    vdown[n+1][j] = true;
    for(int i=n; i>=0; --i)
      if (field[i][j] == '.')
        vdown[i][j] = true;
      else if (field[i][j] == 'S')
      {
        vdown[i][j] = true;
        out.push({i, j});
        break;
      }
      else
        break;
  }

  vleft.resize( n + 2, vector<bool>(m+2, false) );
  for(int i=0; i<n+2; ++i)
  {
    vleft[i][0] = true;
    for(int j=1; j<m+2; ++j)
      if (field[i][j] == '.')
        vleft[i][j] = true;
      else if(field[i][j] == 'W')
      {
        vleft[i][j] = true;
        out.push({i, j});
        break;
      }
      else
        break;
  }

  vright.resize( n + 2, vector<bool>(m+2, false) );
  for(int i=0; i<n+2; ++i)
  {
    vright[i][m+1] = true;
    for(int j=m; j>=0; --j)
      if (field[i][j] == '.')
        vright[i][j] = true;
      else if(field[i][j] == 'E')
      {
        vright[i][j] = true;
        out.push({i, j});
        break;
      }
      else
        break;
  }
}

int main()
{
  read_data();
  solve();
  return 0;
}