#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define X first #define Y second #define SZ(x) int(x.size()) mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MXN = 505; int n, m, dis[MXN][MXN][4]; char a[MXN][MXN]; int id[256]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> a[i][j]; if(n+m==2) return cout << "0\n", 0; if(a[0][0]=='X') return cout << "-1\n", 0; memset(dis, -1, sizeof(dis)); deque<pair<pii, int>> q; id['E'] = 1; id['S'] = 2; id['W'] = 3; dis[0][0][id[a[0][0]]] = 0; q.push_back({{0, 0}, id[a[0][0]]}); while(!q.empty()) { auto [x, y] = q.front().X; int d = q.front().Y; q.pop_front(); if(dis[x][y][(d+1)%4]==-1) { dis[x][y][(d+1)%4] = dis[x][y][d]+1; q.push_back({{x, y}, (d+1)%4}); } int xx = x+dx[d], yy = y+dy[d]; if(xx<0 || x>=n || yy<0 || yy>=m) continue; if(dis[xx][yy][id[a[xx][yy]]]==-1) { dis[xx][yy][id[a[xx][yy]]] = dis[x][y][d]; if(a[xx][yy]!='X') q.push_front({{xx, yy}, id[a[xx][yy]]}); } } cout << dis[n-1][m-1][id[a[n-1][m-1]]] << '\n'; return 0; }