#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; typedef pair PP; typedef pair PPP; vector dx={1,1,-1,-1}; vector dy={1,-1,1,-1}; void solve(){ int h,w; cin >> h >> w; vector s(h); vector>> d(2,vector>(h,vector(w,mod))); vector>> visited(2,vector>(h,vector(w,false))); int sx,sy,gx,gy; rep(i,h){ cin >> s[i]; rep(j,w){ if(s[i][j]=='S'){ sy=i;sx=j; } if(s[i][j]=='G'){ gy=i,gx=j; } } } queue que; que.push(PPP(0,PP(0,P(sy,sx)))); d[0][sy][sx]=0;visited[0][sy][sx]=true; while(!que.empty()){ PPP ppp=que.front();que.pop(); int k=ppp.first,q=ppp.second.first,y=ppp.second.second.first,x=ppp.second.second.second; //cout << q << " " << y << " " << x << " " << k << endl; rep(i,4){ if(q==0){ int ny=y+2*dy[i],nx=x+dx[i]; if(ny=0 && nx=0){ int nq=(s[ny][nx]=='R'); if(!visited[nq][ny][nx]){ d[nq][ny][nx]=k+1; visited[nq][ny][nx]=true; que.push(PPP(k+1,PP(nq,P(ny,nx)))); } } ny=y+dy[i],nx=x+2*dx[i]; if(ny=0 && nx=0){ int nq=(s[ny][nx]=='R'); if(visited[nq][ny][nx]) continue; d[nq][ny][nx]=k+1; visited[nq][ny][nx]=true; que.push(PPP(k+1,PP(nq,P(ny,nx)))); } } if(q==1){ int ny=y+dy[i],nx=x+dx[i]; if(ny=0 && nx=0){ int nq=1-(s[ny][nx]=='R'); if(visited[nq][ny][nx]) continue; d[nq][ny][nx]=k+1; visited[nq][ny][nx]=true; que.push(PPP(k+1,PP(nq,P(ny,nx)))); } } } } if(visited[0][gy][gx] || visited[1][gy][gx]){ cout << min(d[0][gy][gx],d[1][gy][gx]) << endl; } else{ cout << -1 << endl; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }