#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; const int nx = 505, INF = 2e9; int m, n, sdist[nx][nx] = {0}, rotcost[4] = {0, 1, 2, 3}; ii dir[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; string grid[nx]; bool visited[nx][nx] = {false}; priority_queue<pair<int, ii> , vector<pair<int, ii>>, greater<pair<int, ii>>> pq; int main(){ cin.tie(NULL)->sync_with_stdio(false); cin >> m >> n; for(int i=0; i<m; i++) cin >> grid[i]; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ sdist[i][j] = INF; } } sdist[0][0] = 0; pq.push({0, {0, 0}}); while(!pq.empty()){ auto [rot, pnt] = pq.top(); // cout << rot << ' ' << pnt.first << ' ' << pnt.second << "\n"; pq.pop(); if(visited[pnt.first][pnt.second]) continue; visited[pnt.first][pnt.second] = true; char room = grid[pnt.first][pnt.second]; if(room=='X') continue; for(int i=0; i<4; i++){ // cout << "i = " << i << "\n"; int ty = pnt.first+dir[i].first, tx = pnt.second+dir[i].second; if(ty<0 || ty>=m || tx<0 || tx>=n || visited[ty][tx]) continue; if(room=='N'){ if(sdist[ty][tx]>rot+(i%4)){ sdist[ty][tx] = rot+(i%4); pq.push({sdist[ty][tx], {ty, tx}}); // cout << "roomN push\n"; } } else if(room=='W'){ if(sdist[ty][tx]>rot+((i+1)%4)){ sdist[ty][tx] = rot+((i+1)%4); pq.push({sdist[ty][tx], {ty, tx}}); // cout << "roomW push\n"; } } else if(room=='S'){ if(sdist[ty][tx]>rot+((i+2)%4)){ sdist[ty][tx] = rot+((i+2)%4); pq.push({sdist[ty][tx], {ty, tx}}); // cout << "roomS push\n"; } } else{ if(sdist[ty][tx]>rot+((i+3)%4)){ sdist[ty][tx] = rot+((i+3)%4); pq.push({sdist[ty][tx], {ty, tx}}); // cout << "roomE push\n"; } } } } cout << (sdist[m-1][n-1]==INF ? -1 : sdist[m-1][n-1]); return 0; }