/* * Problem link * */ #include using namespace std; bool inner(int v, int lb, int ub) { return lb <= v&&v <=ub; } struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init; const int INF = (int)1e7; const int dr[2][8] = { {1,1,-1,-1,2,-2,2,-2},{ 1,1,-1,-1,1,1,-1,-1 } }; const int dc[2][8] = { {2,-2,2,-2,1,1,-1,-1},{ 1,-1,-1,1,1,-1,-1,1 } }; int main() { #ifdef INPUT_FROM_FILE ifstream cin("sample.in"); ofstream cout("sample.out"); #endif int R, C; cin >> R >> C; vector S(R); for (auto& it : S)cin >> it; int sr, sc, gr, gc; for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (S[r][c] == 'S')sr = r, sc = c; else if (S[r][c] == 'G')gr = r, gc = c; vector>> NB(2,vector>(R, vector(C, INF))); NB[0][sr][sc] = 0; queue> que; que.push(vector{0, sr, sc}); while (que.empty() == false) { auto v = que.front(); que.pop(); int type = v[0]; int r = v[1]; int c = v[2]; for (int i = 0; i < 8; i++) { int nr = r + dr[type][i]; int nc = c + dc[type][i]; if (inner(nr, 0, R - 1) && inner(nc, 0, C - 1)) { int nt = type ^ (S[nr][nc] == 'R'); if (NB[nt][nr][nc]> NB[type][r][c] + 1) { NB[nt][nr][nc] = NB[type][r][c] + 1; que.push(vector{nt, nr, nc}); } } } } int res = min(NB[0][gr][gc], NB[1][gr][gc]); if (res == INF)res = -1; cout << res << endl; return 0; }