#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair Pr; ll INF = 1000000000; int H, W; int sx, sy, gx, gy; char board[502][502]; ll d[502][502][2]; queue,char>> q; int dx_n[] = { -1,1,-2,2,-1,1,-2,2 }; int dy_n[] = { 2,-2,1,-1,-2,2,-1,1 }; int dx_m[] = { 1,-1,1,-1 }; int dy_m[] = { -1,1,1,-1 }; int main() { cin >> H >> W; for (int i = 1; i <= H; i++) { for (int j = 1; j <=W; j++) { cin >> board[i][j]; if (board[i][j] == 'S') { sx = j, sy = i; } if (board[i][j] == 'G') { gx = j, gy = i; } } } for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) for (int k = 0; k < 2; k++) d[i][j][k] = (ll)INF; q.push({{sx,sy},'N'}); d[sy][sx][1] = 0; while (!q.empty()) { int x = q.front().first.first; int y = q.front().first.second; char c = q.front().second; q.pop(); if (c == 'N') { for (int i = 0; i < 8; i++) { char now = c; int ddx = dx_n[i] + x, ddy = dy_n[i] + y; if (ddx >= 1 && ddx <= W && ddy >= 1 && ddy <= H) { if (board[ddy][ddx] == 'R') { now = 'M'; } if(now == 'N') { if (d[ddy][ddx][1] > d[y][x][1] + 1) { d[ddy][ddx][1] = d[y][x][1] + 1; q.push({ {ddx,ddy},now }); } } else if (now == 'M') { if (d[ddy][ddx][0] > d[y][x][1] + 1) { d[ddy][ddx][0] = d[y][x][1] + 1; q.push({ { ddx,ddy },now}); } } } } } else if (c == 'M') { for (int i = 0; i < 4; i++) { char now = c; int ddx = dx_m[i] + x, ddy = dy_m[i] + y; if (ddx >= 1 && ddx <= W && ddy >= 1 && ddy <= H) { if (board[ddy][ddx] == 'R') { now = 'N'; } if (now == 'M') { if (d[ddy][ddx][0] > d[y][x][0] + 1) { d[ddy][ddx][0] = d[y][x][0] + 1; q.push({ { ddx,ddy },now }); } } else if (now == 'N') { if (d[ddy][ddx][1] > d[y][x][0] + 1) { d[ddy][ddx][1] = d[y][x][0] + 1; q.push({ { ddx,ddy },now }); } } } } } } ll ans = min(d[gy][gx][0], d[gy][gx][1]); if (ans != INF) { cout << ans << endl; } else cout << -1 << endl; return 0; }