#include using namespace std; class Node{ public: int x,y,cost; bool isWall,isGoal; int id; int pre; int type; public: Node(int nx,int ny,int ncost,bool ng,int nid,int npre,int ntype){ x = nx;//X y = ny;//Y cost = ncost;//このノードまでのコスト isGoal = ng;//ゴールかどうか id = nid;//自身のID pre = npre;//ひとつ前のノードのID type = ntype;//1 or 2 (1は♞2はミニビショップ) } }; class NodeList{ public: // iteratorをtypedefする typedef vector::iterator iterator; typedef vector::const_iterator const_iterator; // begin, end iterator begin(){ return datas.begin(); } const_iterator begin() const { return datas.begin(); } iterator end(){ return datas.end(); } const_iterator end() const { return datas.end(); } public: vector datas; // OpenListまたはCloseList. void push_data(Node n){ datas.push_back(n); } void remove(vector::iterator iterator){ datas.erase(iterator); } int getSize(){ return datas.size(); } Node getNode(int id){ vector::iterator iterator = datas.begin(); while (iterator != datas.end()){ if(id == (*iterator).id){ return *iterator; } iterator++; }; } Node getMinCost(){ vector::iterator iterator = datas.begin(),result = datas.begin(); int min = (*iterator).cost; while (iterator != datas.end()){ if(min > (*iterator).cost){ result = iterator; } iterator++; } remove(result); return *result; } vector::iterator find(int x,int y,int type){ vector::iterator iterator = datas.begin(); while (iterator != datas.end()){ if((*iterator).x == x and (*iterator).y == y and (*iterator).type == type){ return iterator; } iterator++; } return datas.end(); } bool isFind(vector::iterator it){ return datas.end() == it ? false : true; } }; int ChangeMode(int type,bool red){ if(!red){ return type; }else{ return type == 1 ? 2 : 1; } } int main(){ int n1,n2; cin >> n1 >> n2; char map_char[n1][n2]; Node Start = Node(0,0,0,false,0,-1,1); Node Goal = Node(0,0,0,true,0,-1,0); for(int i = 0;i < n1;i++){ cin >> map_char[i]; } for(int i = 0;i < n1;i++){ for(int j = 0;j < n2;j++){ if(map_char[i][j] == 'S'){ Start.x = i; Start.y = j; }else if(map_char[i][j] == 'G'){ Goal.x = i; Goal.y = j; } } } Node now = Node(0,0,0,0,0,0,0); int pid = 0; Start.id = -1; NodeList openMap; NodeList closeMap; openMap.push_data(Start); int move[2][8][2] = {{{1,2},{-1,2},{-1,-2},{1,-2},{2,1},{-2,1},{-2,-1},{2,-1}}, {{1,1},{1,-1},{-1,-1},{-1,1}}}; int cx,cy; while(true){ if(openMap.getSize() <= 0){ cout << -1 << endl; return 0; } now = openMap.getMinCost();//計算中の中で一番コストの低いノードを取り出す。(同時に削除される。) closeMap.push_data(now);//計算済みのほうへ移動。 if(now.x == Goal.x && now.y == Goal.y)break; for(int i = 0;(now.type == 1 and i < 8) or (now.type == 2 and i < 4);i++){ cx = now.x + move[now.type - 1][i][0]; cy = now.y + move[now.type - 1][i][1]; if((cx < 0) or (cx > (n1 - 1)) or (cy < 0) or (cy > (n2 - 1)))continue; vector::iterator openFind = openMap.find(cx,cy,ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false))); vector::iterator closeFind = closeMap.find(cx,cy,ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false))); if(openMap.isFind(openFind)){ Node ne = *openFind; if(ne.cost >= now.cost+1){ ne.cost = now.cost+1; ne.pre = now.id; } }else if(closeMap.isFind(closeFind)){ Node ne = *closeFind; if(ne.cost >= now.cost+1){ ne.cost = now.cost+1; ne.pre = now.id; closeMap.remove(closeFind); openMap.push_data(ne); } }else{ Node ne = Node(cx,cy,now.cost+1,false,pid,now.id, ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false))); pid++; openMap.push_data(ne); } } } int c = 0; //cout << endl; while(true){ if(now.id < 0)break; //cout << now.id << " (" << now.y+1 << "," << now.x+1 << ") " << now.pre << endl; now = closeMap.getNode(now.pre); c++; } cout << c << endl; }