#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int knight_dx[8] = {1, 1, -1, -1, 2, 2, -2, -2}; constexpr int knight_dy[8] = {2, -2, 2, -2, 1, -1, 1, -1}; constexpr int bishop_dx[4] = {1, 1, -1, -1}; constexpr int bishop_dy[4] = {1, -1, 1, -1}; int dp[505][505][2]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; vector s(H); int sx = 0, sy = 0, gx = 0, gy = 0; for(int i = 0; i < H; ++i){ cin >> s[i]; for(int j = 0; j < W; ++j){ if(s[i][j] == 'S') sx = i, sy = j; if(s[i][j] == 'G') gx = i, gy = j; } } for(int i = 0; i < H; ++i){ for(int j = 0; j < W; ++j){ for(int k = 0; k < 2; ++k){ dp[i][j][k] = INF; } } } dp[sx][sy][0] = 0; using node = tuple; priority_queue, greater> que; que.emplace(0, sx, sy, 0); while(!que.empty()){ auto [d, x, y, t] = que.top(); que.pop(); if(d > dp[x][y][t]) continue; if(t == 0){ for(int i = 0; i < 8; ++i){ int nx = x + knight_dx[i], ny = y + knight_dy[i]; if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue; int nt = s[nx][ny] == 'R' ? (t ^ 1) : t; if(chmin(dp[nx][ny][nt], dp[x][y][t] + 1)){ que.emplace(dp[nx][ny][nt], nx, ny, nt); } } } else{ for(int i = 0; i < 4; ++i){ int nx = x + bishop_dx[i], ny = y + bishop_dy[i]; if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue; int nt = s[nx][ny] == 'R' ? (t ^ 1) : t; if(chmin(dp[nx][ny][nt], dp[x][y][t] + 1)){ que.emplace(dp[nx][ny][nt], nx, ny, nt); } } } } int ans = min(dp[gx][gy][0], dp[gx][gy][1]); if(ans == INF) ans = -1; cout << ans << endl; return 0; }