#include<bits/stdc++.h>
using namespace std;
enum class Location {
Upper = 1,
Left = 2,
Lower = 3,
Right = 4
};
enum class Orientation {
X = -1, //empty
S = 1, //south
E = 2, //east
N = 3, //north
W = 4 //west
};
struct Coord {
int x, y;
Coord(int a = 0, int b = 0) : x(a), y(b) {};
bool operator<(const Coord &other) const {
if (x < other.x) return true;
else if (x > other.x) return false;
else return y < other.y;
}
};
struct Cell {
Coord coord;
Orientation orientation;
Cell(Coord a = Coord(), Orientation b = Orientation::X) : coord(a), orientation(b) {};
};
struct Neighbor {
Coord coord;
int distance;
Neighbor(Coord a = Coord(), int b = 0) : coord(a), distance(b) {};
};
vector<vector<Cell>> grid;
int M, N;
vector<vector<int>> dist;
Orientation getOrientation (char charorientation) {
switch (charorientation) {
case 'S':
return Orientation::S;
case 'E':
return Orientation::E;
case 'N':
return Orientation::N;
case 'W':
return Orientation::W;
default:
return Orientation::X;
}
}
int distToNeigh(Location location, Orientation orientation) {
return (((int)orientation - (int)location)+4)%4;
}
void checkNeigh(Coord curr, Location neighLocation, vector<Neighbor> &result) {
bool exists;
Coord neighCoord;
switch(neighLocation) {
case Location::Upper:
exists = (curr.y > 0);
neighCoord = Coord(curr.x, curr.y - 1);
break;
case Location::Left:
exists = (curr.x > 0);
neighCoord = Coord(curr.x - 1, curr.y);
break;
case Location::Lower:
exists = (curr.y < M - 1);
neighCoord = Coord(curr.x, curr.y + 1);
break;
case Location::Right:
exists = (curr.x < N - 1);
neighCoord = Coord(curr.x + 1, curr.y);
break;
default:
exists = false;
break;
}
if(exists) {
Cell neighCell = grid[neighCoord.x][neighCoord.y];
if(neighCell.orientation != Orientation::X) {
result.push_back(Neighbor(neighCoord, distToNeigh(neighLocation, neighCell.orientation)));
}
}
}
vector<Neighbor> getNeigh(Coord curr) {
vector<Neighbor> result;
for(int i = 1; i <= 4; i++) {
checkNeigh(curr, (Location)i, result);
}
return result;
}
void dijkastra() {
dist[N-1][M-1] = 0;
vector<vector<bool>> done (N, vector<bool>(M));
priority_queue<pair<int, Coord>> q;
q.push({0, Coord(N-1, M-1)});
while(!q.empty()){
Coord curr = q.top().second; q.pop();
if(!done[curr.x][curr.y]) {
done[curr.x][curr.y] = true;
vector<Neighbor> neighs = getNeigh(curr);
for(Neighbor neigh : neighs) {
if(dist[curr.x][curr.y] + neigh.distance < dist[neigh.coord.x][neigh.coord.y] || dist[neigh.coord.x][neigh.coord.y] == -1) {
dist[neigh.coord.x][neigh.coord.y] = dist[curr.x][curr.y] + neigh.distance;
q.push({-dist[neigh.coord.x][neigh.coord.y], neigh.coord});
}
}
}
}
}
int main() {
cin >> M >> N;
grid.resize(N, vector<Cell>(M));
dist.resize(N, vector<int>(M, -1));
for(int y = 0; y < M; y++) {
string row; cin >> row;
for(int x = 0; x < N; x++) {
grid[x][y] = Cell(Coord(x, y), getOrientation(row[x]));
}
}
dijkastra();
cout << dist[0][0] << "\n";
return 0;
}
