#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>
const int MOD = 1'000'000'000 + 7;
void setIO(string name = "")
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef LOCAL
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
if (!name.empty())
{
freopen((name + ".INP").c_str(), "r", stdin);
freopen((name + ".OUT").c_str(), "w", stdout);
}
#endif
}
const int reality[5] = {-1, 4, 2, 1, 3};
inline int cost(int k1, int k2) {
return (reality[k2] - reality[k1] + 4) % 4;
}
const vector<pii> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int n, m;
int a[505][505];
inline int cnv(int i, int j, int state) {
return 5 * ((i - 1) * m + j) + state;
}
inline bool in(int i, int j) {
return i >= 1 && i <= n && j >= 1 && j <= m;
}
unordered_map<int, vector<pii>> g;
unordered_map<int, int> d;
deque<int> buckets[4];
void dial(int source) {
d.clear();
d[source] = 0;
buckets[0].push_back(source);
int inBuckets = 1;
while (inBuckets > 0) {
int id = 0;
while (id <= 3 && buckets[id].empty()) id++;
if (id > 3) break;
int u = buckets[id].front();
buckets[id].pop_front();
inBuckets--;
if (d[u] < id) continue;
for (auto [v, w] : g[u]) {
int newDist = d[u] + w;
if (!d.count(v) || newDist < d[v]) {
d[v] = newDist;
buckets[newDist % 4].push_back(v);
inBuckets++;
}
}
}
}
void solve() {
cin >> n >> m;
g.clear();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c; cin >> c;
a[i][j] = (c == 'X' ? 0 : c == 'W' ? 1 : c == 'E' ? 2 : c == 'N' ? 3 : 4);
}
}
if (a[1][1] == 0 || a[n][m] != 0) {
cout << -1 << '\n';
return;
}
for (int state = 1; state <= 4; state++) {
g[0].emplace_back(cnv(1, 1, state), 0);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0) continue;
for (int k = 1; k <= 4; k++) {
int x = i + directions[k - 1].f;
int y = j + directions[k - 1].s;
if (!in(x, y)) continue;
for (int k1 = (a[x][y] != 0 ? 1 : 0); k1 <= (a[x][y] == 0 ? 0 : 4); k1++) {
g[cnv(i, j, k)].emplace_back(cnv(x, y, k1), cost(a[i][j], k));
}
}
}
}
dial(0);
if (!d.count(cnv(n, m, 0)) || d[cnv(n, m, 0)] == INF) {
cout << -1 << '\n';
} else {
cout << d[cnv(n, m, 0)] << '\n';
}
}
signed main()
{
setIO();
int t = 1;
// cin >> t;
while (t--)
solve();
}
