#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, sy, gx, gy; 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; } } } vector> g[2][h][w]; REP(i,h){ REP(j,w){ REP(k,4){ int dx = ddx[k], dy = ddy[k]; // cout << endl; DEBUG(i); DEBUG(j); int ni = i+dx, nj = j+dy*2; DEBUG(ni); DEBUG(nj); if(0 <= ni and ni < h and 0 <= nj and nj < w){ if(s[ni][nj] != 'R'){ g[0][i][j].push_back(make_tuple(0,ni,nj)); }else{ g[0][i][j].push_back(make_tuple(1,ni,nj)); } } ni = i+2*dx; nj = j+dy; DEBUG(ni); DEBUG(nj); if(0 <= ni and ni < h and 0 <= nj and nj < w){ if(s[ni][nj] != 'R'){ g[0][i][j].push_back(make_tuple(0,ni,nj)); }else{ g[0][i][j].push_back(make_tuple(1,ni,nj)); } } } } } REP(i,h){ REP(j,w){ REP(k,4){ int ni = i+dx[k], nj = j+dy[k]; if(0 <= ni and ni < h and 0 <= nj and nj < w){ if(s[ni][nj] != 'R'){ g[1][i][j].push_back(make_tuple(1,ni,nj)); }else{ g[1][i][j].push_back(make_tuple(0,ni,nj)); } } } } } 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()){ auto t = qu.front(); qu.pop(); int a = get<0>(t); int b = get<1>(t); int c = get<2>(t); if(b == gx and c == gy){ cout << get<3>(t) << endl; return 0; } gf[a][b][c] = true; RBP(tup,g[a][b][c]){ if(!gf[get<0>(tup)][get<1>(tup)][get<2>(tup)]){ qu.push(tuple_cat(tup,make_tuple(get<3>(t)+1))); } } } cout << -1 << endl; return 0; }