#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 ull = unsigned long long; using ll = long long; using lli = long long int; using ld = long double; using pa = pair; using ppa = pair; #define SORT(v, n) sort(v, v+n); #define ALL(v) v.begin(),v.end() #define VSORT(v) sort(ALL(v)) #define GRESORT(v) sort(ALL(v),greater()) #define REVERSE(v) reverse(ALL(v)) #define overlap(v) v.erase(unique(ALL(v)),v.end()) #define debug(x) cout << #x << ": " << x << endl #define FOR(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i = (b-1); i >= a; i--) #define rrep(i,n) RFOR(i,0,n) #define INF 999999999 #define mins(a,b) a = min(a,b) #define maxs(a,b) a = max(a,b) //4近傍 //int dy[]={0, 1, 0, -1}; //int dx[]={1, 0, -1, 0}; //8近傍 //int dy[]={0,0,1,-1,1,1,-1,-1}; //int dx[]={1,-1,0,0,1,-1,1,-1}; //knight int kdy[] = {-2,-2,-1,-1,1,1,2,2}; int kdx[] = {-1,1,-2,2,-2,2,-1,1}; //bishop int bdy[] = {1,1,-1,-1}; int bdx[] = {1,-1,1,-1}; ll mod = 1000000007; bool check(int x, int y, int h, int w){ return (x < 0 || y < 0 || y >= h || x >= w); } void solve() { int h,w; cin >> h >> w; char c[510][510]; int sx,sy,gx,gy; int d[510][510][2] = {}; rep(i,h){ rep(j,w){ cin >> c[i][j]; if(c[i][j] == 'S'){ sy = i; sx = j; } if(c[i][j] == 'G'){ gy = i; gx = j; } d[i][j][0] = INF; d[i][j][1] = INF; } } d[sy][sx][0] = 0; queue q; q.push(ppa(pa(sx,sy),0)); while(!q.empty()){ ppa p = q.front(); q.pop(); pa pp = p.first; int x = pp.first, y = pp.second, r = p.second; //debug(x); debug(y); debug(r); if(gx == x && gy == y) break; if(r == 0){ rep(i,8){ int xx = x + kdx[i]; int yy = y + kdy[i]; if(check(xx,yy,h,w)) continue; int nr = r ^ (c[yy][xx] == 'R' ? 1 : 0); if(d[yy][xx][nr] == INF){ d[yy][xx][nr] = d[y][x][r] + 1; q.push(ppa(pa(xx,yy),nr)); } } }else{ rep(i,4){ int xx = x + bdx[i]; int yy = y + bdy[i]; if(check(xx,yy,h,w)) continue; int nr = r ^ (c[yy][xx] == 'R' ? 1 : 0); if(d[yy][xx][nr] == INF){ d[yy][xx][nr] = d[y][x][r] + 1; q.push(ppa(pa(xx,yy),nr)); } } } } cout << (d[gy][gx][0] != INF || d[gy][gx][1] != INF ? min(d[gy][gx][0],d[gy][gx][1]) : -1) << endl; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); solve(); return 0; }