#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1000000007;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int m,n;
cin >> m >> n;
set<pair<int, pair<int, int>>> cache;
char board[m][n];
int distances[m][n];
bool fixed[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
cin >> board[i][j];
distances[i][j] = INF;
fixed[i][j] = 0;
}
}
//Dijkstra !
distances[0][0] = 0;
cache.insert({0, {0,0}});
while(cache.size()){
auto k = *cache.begin();
cache.erase(cache.begin());
if(board[k.second.first][k.second.second] == 'X') {
fixed[k.second.first][k.second.second] = 1;
continue;
}
// E
if(board[k.second.first][k.second.second] == 'E') {
fixed[k.second.first][k.second.second] = 1;
if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1]
&& distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 0){
cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 0;
cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
}
// S
if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second]
&& distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 1){
cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 1;
cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
}
// W
if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1]
&& distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 2){
cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 2;
cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
}
// N
if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second]
&& distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 3){
cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 3;
cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
}
continue;
}
// S
if(board[k.second.first][k.second.second] == 'S') {
fixed[k.second.first][k.second.second] = 1;
if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1]
&& distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 3){
cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 3;
cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
}
// S
if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second]
&& distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 0){
cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 0;
cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
}
// W
if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1]
&& distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 1){
cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 1;
cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
}
// N
if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second]
&& distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 2){
cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 2;
cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
}
continue;
}
// W
if(board[k.second.first][k.second.second] == 'W') {
fixed[k.second.first][k.second.second] = 1;
if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1]
&& distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 2){
cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 2;
cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
}
// S
if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second]
&& distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 3){
cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 3;
cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
}
// W
if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1]
&& distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 0){
cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 0;
cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
}
// N
if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second]
&& distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 1){
cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 1;
cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
}
continue;
}
// N
if(board[k.second.first][k.second.second] == 'N') {
fixed[k.second.first][k.second.second] = 1;
if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1]
&& distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 1){
cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 1;
cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
}
// S
if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second]
&& distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 2){
cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 2;
cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
}
// W
if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1]
&& distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 3){
cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 3;
cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
}
// N
if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second]
&& distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 0){
cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 0;
cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
}
continue;
}
}
cout << (distances[m-1][n-1] == INF ? -1 : distances[m-1][n-1]) << '\n';
}
