#include using namespace std; typedef long long int64; int W, H; char mas[500][500]; int min_cost[2][500][500]; int bfs(int sx, int sy, char c) { static const int vx[] = {-1, 1, -2, 2, -2, 2, -1, 1}, vy[] = {-2, -2, -1, -1, 1, 1, 2, 2}; static const int dx[] = {-1, 1, -1, 1}, dy[] = {-1, -1, 1, 1}; memset(min_cost, -1, sizeof(min_cost)); queue< pair< bool, pair< int, int > > > que; que.push({0, {sx, sy}}); min_cost[0][sx][sy] = 0; while(!que.empty()) { auto p = que.front().second; int type = que.front().first; que.pop(); if(mas[p.second][p.first] == c) return(min_cost[type][p.first][p.second]); for(int i = 0; i < (type ? 4 : 8); i++) { int nx = p.first + (type ? dx[i] : vx[i]); int ny = p.second + (type ? dy[i] : vy[i]); if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue; bool flip = mas[ny][nx] == 'R'; if(min_cost[type ^ flip][nx][ny] != -1) continue; min_cost[type ^ flip][nx][ny] = min_cost[type][p.first][p.second] + 1; que.push({type ^ flip, {nx, ny}}); } } return(-1); } int main() { cin >> H >> W; int sx, sy; for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { cin >> mas[i][j]; if(mas[i][j] == 'S') sx = j, sy = i; } } cout << bfs(sx, sy, 'G') << endl; }