#include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) using namespace std; const vector knight_move_y { 1, 2, 2, 1, -1, -2, -2, -1 }; const vector knight_move_x { 2, 1, -1, -2, -2, -1, 1, 2 }; const vector bishop_move_y { 1, 1, -1, -1 }; const vector bishop_move_x { 1, -1, -1, 1 }; const int inf = 1e9+7; int main() { // input int h, w; cin >> h >> w; vector s(h); repeat (y,h) cin >> s[y]; // prepare auto on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; }; int gy, gx, sy, sx; repeat (y,h) repeat (x,w) { switch (s[y][x]) { case 'S': sy = y; sx = x; break; case 'G': gy = y; gx = x; break; } } // bfs vector > > dp(2, vector >(h, vector(w, inf))); queue > que; que.push(make_tuple(false, gy, gx)); dp[0][gy][gx] = 0; while (not que.empty()) { bool bishop; int y, x; tie(bishop, y, x) = que.front(); que.pop(); vector const & dy = bishop ? bishop_move_y : knight_move_y; vector const & dx = bishop ? bishop_move_x : knight_move_x; int len = dy.size(); repeat (i,len) { int ny = y + dy[i]; int nx = x + dx[i]; if (not on_field(ny, nx)) continue; bool nbishop = s[ny][nx] == 'R' ? not bishop : bishop; if (dp[nbishop][ny][nx] == inf) { dp[nbishop][ny][nx] = dp[bishop][y][x] + 1; que.push(make_tuple(nbishop, ny, nx)); } } } // output int ans = min(dp[0][sy][sx], dp[1][sy][sx]); if (ans == inf) ans = -1; cout << ans << endl; return 0; }