#include using namespace std; #define INF 1000000000 #define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define MAX_V 500000 struct edge {int to,cost;}; typedef pair P; //firstは最短距離,secondは頂点の番号 int V; vector G[MAX_V]; int d[MAX_V]; int H,W; int sx,sy; int gx,gy; int check[501][501]; int dp[2][501][501]; int ni_x[8]={-2,-1,1,2,-2,-1,1,2}; int ni_y[8]={1,2,2,1,-1,-2,-2,-1}; int bi_x[4]={-1,1,-1,1}; int bi_y[4]={1,1,-1,-1}; struct gli{ int cost; int c;//1ナイト0ミニビショップ int x; int y; }; bool operator <(const gli& g,const gli& g2){ return g.cost(const gli& g,const gli& g2){ return g.cost>g2.cost; } bool check_range(int x,int y){ if(x<0||x>=H||y<0||y>=W)return false; return true; } void dijkstra(int x,int y){ priority_queue,greater > que; gli g1={0,1,x,y}; //gli g2={0,1,x,y}; dp[1][x][y]=0; que.push(g1); //que.push(g2); while(!que.empty()){ gli g=que.top();que.pop(); if(dp[g.c][g.x][g.y]g.cost+1){ dp[c][xx][yy]=g.cost+1; gli gg={g.cost+1,c,xx,yy}; que.push(gg); } } } }else{ REP(i,4){ int xx=bi_x[i]+g.x; int yy=bi_y[i]+g.y; int c=g.c; if(check_range(xx,yy)){ if(check[xx][yy]==1)c=1-c; if(dp[c][xx][yy]>g.cost+1){ dp[c][xx][yy]=g.cost+1; gli gg={g.cost+1,c,xx,yy}; que.push(gg); } } } } } } int main(){ cin>>H>>W; REP(i,H){ REP(j,W){ check[i][j]=0; } } REP(i,2){ REP(j,H){ REP(k,W){ dp[i][j][k]=INF; } } } REP(i,H){ string s; cin>>s; REP(j,W){ if(s[j]=='R'){ check[i][j]=1; } if(s[j]=='S'){ sx=i;sy=j; } if(s[j]=='G'){ gx=i;gy=j; } } } dijkstra(sx,sy); /* REP(i,2){ REP(j,H){ REP(k,W){ cout<