UVA 314

#include <bits/stdc++.h>

using namespace std;

int left(int i){
    if(i == 0) return 3;
    else return i-1;
}

int right(int i){
    if(i == 3) return 0;
    else return i+1;
}

int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);

    int n,m;
    while(cin >> n >> m, n || m){
        vector<vector<int>> gin(n, vector<int>(m));
        vector<vector<int>> g(n-1, vector<int>(m-1));

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                cin >> gin[i][j];
            }
        }

        for(int i = 0; i < n-1; ++i){
            for(int j = 0; j < m-1; ++j){
                if(gin[i][j] || gin[i+1][j] || gin[i][j+1] || gin[i+1][j+1])
                    g[i][j] = 1;
                //cout << g[i][j] << "\t";
            }//cout << endl;
        }

        string dir;
        int b1, b2, e1, e2, ori;
        cin >> b1 >> b2 >> e1 >> e2 >> dir;
        b1--;b2--;
        e1--;e2--;

        if(dir[0] == 'n') ori = 0;
        if(dir[0] == 'e') ori = 1;
        if(dir[0] == 's') ori = 2;
        if(dir[0] == 'w') ori = 3;

        struct Pos{
            int x,y,dir;
        };
        int d[n][m][4];
        memset(d, -1, sizeof(d));
        queue<Pos> q;
        q.push({b1,b2,ori});
        d[b1][b2][ori] = 0;

        int roff[]{-1,0,1,0};
        int coff[]{0,1,0,-1};
        int resp = -1;

        while(!q.empty()){
            auto p = q.front(); q.pop();
            //cout << p.x << " " << p.y << " " << p.dir << endl;
            if(p.x == e1 && p.y == e2){
                resp = d[p.x][p.y][p.dir];
                break;
            }

            if(d[p.x][p.y][right(p.dir)] == -1){
                d[p.x][p.y][right(p.dir)] = d[p.x][p.y][p.dir] + 1;
                q.push({p.x,p.y,right(p.dir)});
            }

            if(d[p.x][p.y][left(p.dir)] == -1){
                d[p.x][p.y][left(p.dir)] = d[p.x][p.y][p.dir] + 1;
                q.push({p.x,p.y,left(p.dir)});
            }

            for(int i = 1; i <= 3; ++i){
                int r = p.x + roff[p.dir]*i;
                int c = p.y + coff[p.dir]*i;

                if(r >= 0 && r < n-1 && c >= 0 && c < m-1){
                    if(g[r][c]) break;
                    if(d[r][c][p.dir] == -1){
                        d[r][c][p.dir] = d[p.x][p.y][p.dir] + 1;
                        q.push({r,c,p.dir});
                    }
                }
            }
        }
        cout << resp << endl;
        // for(int k = 0; k < 4; ++k){
            // for(int i = 0; i < n-1; ++i){
                // for(int j = 0; j < m-1; ++j){
                    // cout << d[i][j][k] << "\t";
                // }cout << endl;
            // }
            // cout << endl;
        // }
    }

    return 0;

}