#include "bits/stdc++.h" using namespace std; #define int long long #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(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define REP1(i, n) for(int i=1; i<=(n); i++) #define RREP1(i, n) for(int i=(n); i>=1; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define out(...) printf(__VA_ARGS__) int dxy[] = {1,2, 2,1, -1,-2, -2,-1, 1,2}; int dxy2[] = {1,1,-1,-1,1,1}; void solve(); signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; } /*================================*/ #if DEBUG #define SIZE 4 #else #define SIZE 555 #endif int H,W; int MAP[SIZE][SIZE]; int START=1,GOAL=2,RED=3; struct P { int h,w,t; P(int h, int w, int t):h(h),w(w),t(t){}; bool operator < (const P& p) const { return p.t > t; } }; typedef pair Q; priority_queue, greater> que; int DP[2][SIZE][SIZE]; int N=0,B=1; P *goal; void solve() { cin>>H>>W; string s; REP(i,2)REP(h,H)REP(w,W)DP[i][h][w]=INT_MAX; REP(h,H) { cin>>s; REP(w,W) { if (s[w]=='S') { MAP[h][w]=START; DP[N][h][w]=0; que.push(Q(0,P(h,w,N))); } if (s[w]=='G') { MAP[h][w]=GOAL; goal = new P(h,w,0); } if (s[w]=='R') MAP[h][w]=RED; } } while(que.size()) { auto item = que.top(); que.pop(); auto p = item.second; if (DP[p.t][p.h][p.w] < item.first) continue; int t = p.t; if (MAP[p.h][p.w]==RED) t = !t; if (t==N) { REP(i,8) { int nh = p.h + dxy[i]; int nw = p.w + dxy[i+2]; int nc = item.first+1; if (nh<0||nw<0||H<=nh||W<=nw) continue; if (DP[t][nh][nw] > nc) { DP[t][nh][nw] = nc; que.push(Q(nc, P(nh,nw,t))); } } } if (t==B) { REP(i,4) { int nh = p.h + dxy2[i]; int nw = p.w + dxy2[i+1]; int nc = item.first+1; if (nh<0||nw<0||H<=nh||W<=nw) continue; if (DP[t][nh][nw] > nc) { DP[t][nh][nw] = nc; que.push(Q(nc, P(nh,nw,t))); } } } } int ans = min(DP[N][goal->h][goal->w], DP[B][goal->h][goal->w]); if (ans == INT_MAX) { cout << -1 << endl; } else { cout << ans << endl; } }