UVa Q985

//UVa Q985
#include <bits/stdc++.h>
using namespace std;

bool arr[501][501][4];
bool vis[501][501][4];

//{N,E,S,W}
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

struct stat{
    int step, x, y, t;
};

int32_t main(){
    int n,m;
    string s;
    while(cin >> n >> m){
        memset(vis, 0, sizeof(vis));
        memset(arr, 0, sizeof(arr));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                if(i == n && j == m)break;
                cin >> s;
                for(int k = 0; k < s.size(); ++k){
                    if(s[k] == 'N')arr[i][j][0] = 1;
                    else if(s[k] == 'E')arr[i][j][1] = 1;
                    else if(s[k] == 'S')arr[i][j][2] = 1;
                    else if(s[k] == 'W')arr[i][j][3] = 1;
                }
            }
        }
        stat one = {.step = 0, .x = 1, .y = 1, .t = 0};
        deque<stat> dq;
        dq.emplace_back(one);
        int ans = 0;
        while(!dq.empty() && !ans){
            stat tmd = dq.front();
            dq.pop_front();
            //cout << tmd.x << ' ' << tmd.y << ' ' << tmd.t << ' ' << tmd.step << endl;
            for(int i = 0; i < 4; ++i){
                if(arr[tmd.x][tmd.y][(i-tmd.t+4)%4] == 0)continue;
                stat nxt = {.step = tmd.step+1, .x = tmd.x+dx[i], .y = tmd.y+dy[i], .t = (tmd.t+1) % 4};
                //cout << ' ' << nxt.x << ' ' << nxt.y << ' ' << nxt.t << ' ' << nxt.step << endl;
                if(0 < nxt.x && nxt.x <= n && 0 < nxt.y && nxt.y <= m && !vis[nxt.x][nxt.y][nxt.t]){
                    if(nxt.x == n && nxt.y == m){
                        ans = nxt.step;
                        break;
                    }
                    vis[nxt.x][nxt.y][nxt.t] = 1;
                    dq.emplace_back(nxt);
                }
            }
        }
        if(ans)cout << ans << '\n';
        else cout << "no path to exit\n";
    }
    return 0 ;
}