https://atcoder.jp/contests/abc317/submissions/45000172

include

include <bits/stdc++.h>

using namespace std;

bool isdir(char c){

if(c == '<' || c == '^' || c == '>' || c == 'v')return true;
return false;

}

bool isvalid(int i, int j, int n, int m){

if(i < 0 || j < 0 || i >= n || j >= m)return false;
return true;

}

bool isnotgoal(char c){ if(c == 'S' || c == 'G')return false; return true; }

vector x = {-1, 0, 1, 0}; vector y = {0, 1, 0, -1};

int main() {

int h, w;
cin>>h>>w;

vector<vector<char> > mat(h + 1, vector<char> (w + 1));

int start_i = -1, start_j = -1, final_i = -1, final_j = -1;

for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
        cin>>mat[i][j];
        if(mat[i][j] == 'S'){
            start_i = i;
            start_j = j;
        }

        if(mat[i][j] == 'G'){
            final_i = i;
            final_j = j;
        }
    }
}

// cout<<start_i<<" "<<start_j<<" "<<final_i<<" "<<final_j<<" coordinates \n";

if(start_i == final_i && start_j == final_j)return 0;

for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){

        if(isdir(mat[i][j])){

            char dir = mat[i][j];
            int row = i, col = j;

            if(dir == '<'){
                col--;
                while(col >= 0 && mat[row][col] != '#' && !isdir(mat[row][col]) && isnotgoal(mat[row][col])){
                    mat[row][col] = '#';
                    col--;
                }
            }
            if(dir == '^'){
                row--;
                while(row >= 0 && mat[row][col] != '#' && !isdir(mat[row][col]) && isnotgoal(mat[row][col])){
                    mat[row][col] = '#';
                    row--;
                }
            }
            if(dir == '>'){
                col++;
                while(col < w && mat[row][col] != '#' && !isdir(mat[row][col]) && isnotgoal(mat[row][col])){
                    mat[row][col] = '#';
                    col++;
                }
            }
            if(dir == 'v'){
                row++;
                while(row < h && mat[row][col] != '#' && !isdir(mat[row][col]) && isnotgoal(mat[row][col])){
                    mat[row][col] = '#';
                    row++;
                }
            }

        }

    }
}

// for(int i = 0; i < h; i++){ // for(int j = 0; j < w; j++)cout<<mat[i][j]<<" "; // cout<<"\n"; // }

vector<vector<bool> > vis(h + 1, vector<bool> (w + 1, false));
queue<pair<pair<int, int>, int > > q;

int level = INT_MAX;

q.push({{start_i, start_j}, 0});
vis[start_i][start_j] = true;

while(!q.empty()){

    int curr_i, curr_j;
    auto p = q.front();
    q.pop();

    curr_i = p.first.first;
    curr_j = p.first.second;
    int curr_level = p.second;

    if(curr_i == final_i && curr_j == final_j){
        level = curr_level;
        break;
    }

    for(int i = 0; i < 4; i++){

        int row = curr_i + x[i];
        int col = curr_j + y[i];

        if(isvalid(row, col, h, w) && !vis[row][col] && mat[row][col] != '#' && !isdir(mat[row][col])){

            vis[row][col] = true;
            q.push({{row, col}, curr_level + 1});

        }

    }

}
cout<<(level == INT_MAX ? -1 : level)<<"\n";

return 0;

}