#include #include #include #include #include #include #include #include using namespace std; int mapf[501][501]; int dp[501][501][2]; int w,h; inline bool inbox(int x,int y){ return (0<=x && 0<=y && x> h>>w; for (y=0;y> ch),(ch!='S'&&ch!='G'&&ch!='R'&&ch!='.')); if (ch=='S'){ sx=x;sy=y; } if (ch=='G'){ gx=x;gy=y; } mapf[x][y]=ch; } } priority_queue,vector>, function&,vector&)>> qu([](vector &vl,vector &vr){return vl[4]>vr[4];}); qu.push(vector{sx,sy,0,0,0}); while (!qu.empty()){ vector e=qu.top(); qu.pop(); x=e[0];y=e[1]; if (mapf[x][y]=='R') e[2]=!e[2]; if (mapf[x][y]=='G'){ cout << e[3] << endl; return 0; } dp[x][y][e[2]]=1; k=abs(x-gx)+abs(y-gy); e[3]++; if (!e[2]){ if (inbox(x-2,y-1)&& !dp[x-2][y-1][0]) qu.push(vector{x-2,y-1,e[2],e[3],-k}); if (inbox(x-2,y+1)&& !dp[x-2][y+1][0]) qu.push(vector{x-2,y+1,e[2],e[3],-k}); if (inbox(x-1,y-2)&& !dp[x-1][y-2][0]) qu.push(vector{x-1,y-2,e[2],e[3],-k}); if (inbox(x-1,y+2)&& !dp[x-1][y+2][0]) qu.push(vector{x-1,y+2,e[2],e[3],-k}); if (inbox(x+2,y-1)&& !dp[x+2][y-1][0]) qu.push(vector{x+2,y-1,e[2],e[3],-k}); if (inbox(x+2,y+1)&& !dp[x+2][y+1][0]) qu.push(vector{x+2,y+1,e[2],e[3],-k}); if (inbox(x+1,y-2)&& !dp[x+1][y-2][0]) qu.push(vector{x+1,y-2,e[2],e[3],-k}); if (inbox(x+1,y+2)&& !dp[x+1][y+2][0]) qu.push(vector{x+1,y+2,e[2],e[3],-k}); }else{ if (inbox(x-1,y-1)&& !dp[x-1][y-1][1]) qu.push(vector{x-1,y-1,e[2],e[3],-k}); if (inbox(x-1,y+1)&& !dp[x-1][y+1][1]) qu.push(vector{x-1,y+1,e[2],e[3],-k}); if (inbox(x+1,y-1)&& !dp[x+1][y-1][1]) qu.push(vector{x+1,y-1,e[2],e[3],-k}); if (inbox(x+1,y+1)&& !dp[x+1][y+1][1]) qu.push(vector{x+1,y+1,e[2],e[3],-k}); } } cout << -1 << endl; return 0; }