#include using namespace std; #define endl '\n' #define PB push_back #define ALL(a) (a).begin(),(a).end() #define SZ(a) int((a).size()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define RBP(i,a) for(auto& i : a) #ifdef LOCAL111 #define DEBUG(x) cout<<#x<<": "<<(x)< P; typedef long long int LL; typedef unsigned long long ULL; typedef pair LP; void ios_init(){ ios::sync_with_stdio(false); cin.tie(0); //cout.setf(ios::fixed); //cout.precision(12); } int dx[] = {0,1,0,-1}; int dy[] = {0,-1,0,1}; int ddx[] = {1,-1,1,-1}; int ddy[] = {-1,1,1,-1}; int main() { ios_init(); int h,w; cin >> h >> w; vector s(h); REP(i,h){ cin >> s[i]; } int sx = -1, sy = -1, gx = -1, gy = -1; REP(i,h){ REP(j,w){ if(s[i][j] == 'S'){ sx = i; sy = j; }else if(s[i][j] == 'G'){ gx = i; gy = j; } } } bool gf[2][h][w]; fill(gf[0][0],gf[2][0],false); queue> qu; qu.push(make_tuple(0,sx,sy,0)); while(!qu.empty()){ DEBUG(SZ(qu)); auto t = qu.front(); qu.pop(); int a = get<0>(t); int b = get<1>(t); int c = get<2>(t); if(gf[a][b][c]) continue; if(b == gx and c == gy){ cout << get<3>(t) << endl; return 0; } DEBUG(a); DEBUG(b); DEBUG(c); gf[a][b][c] = true; if(a){ REP(k,4){ int ni = b+dx[k], nj = c+dy[k]; if(0 <= ni and ni < h and 0 <= nj and nj < w){ if(s[ni][nj] != 'R'){ if(!gf[1][ni][nj]) qu.push(make_tuple(1,ni,nj,get<3>(t)+1)); }else{ if(!gf[0][ni][nj]) qu.push(make_tuple(0,ni,nj,get<3>(t)+1)); } } } }else{ REP(k,4){ int dx = ddx[k], dy = ddy[k]; int ni = b+dx, nj = c+dy*2; if(0 <= ni and ni < h and 0 <= nj and nj < w){ if(s[ni][nj] != 'R'){ if(!gf[0][ni][nj]) qu.push(make_tuple(0,ni,nj,get<3>(t)+1)); }else{ if(!gf[1][ni][nj]) qu.push(make_tuple(1,ni,nj,get<3>(t)+1)); } } ni = b+2*dx; nj = c+dy; if(0 <= ni and ni < h and 0 <= nj and nj < w){ if(s[ni][nj] != 'R'){ if(!gf[0][ni][nj]) qu.push(make_tuple(0,ni,nj,get<3>(t)+1)); }else{ if(!gf[1][ni][nj]) qu.push(make_tuple(1,ni,nj,get<3>(t)+1)); } } } } } cout << -1 << endl; return 0; }