#include #include #include using namespace std; const int BUF = 505; class Data { public: bool type; int r, c; Data(){} Data(bool type, int r, int c): type(type), r(r), c(c){} }; int row, col; int bgnR, bgnC; int endR, endC; bool isRed[BUF][BUF]; void read() { memset(isRed, 0, sizeof(isRed)); cin >> row >> col; for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { char ch; cin >> ch; isRed[i][j] = ch == 'R'; if (ch == 'S') { bgnR = i; bgnC = j; } if (ch == 'G') { endR = i; endC = j; } } } } void work() { queue Q; int cost[2][BUF][BUF]; memset(cost, -1, sizeof(cost)); Q.push(Data(0, bgnR, bgnC)); cost[0][bgnR][bgnC] = 0; while (!Q.empty()) { Data curr = Q.front(); Q.pop(); if (curr.r == endR && curr.c == endC) { cout << cost[curr.type][curr.r][curr.c] << endl; return; } // knight の動き static int kdr[] = {-2, -1, 1, 2, 2, 1, -1, -2}; static int kdc[] = { 1, 2, 2, 1, -1, -2, -2, -1}; // mini bishop の動き static int bdr[] = {-1, 1, 1, -1}; static int bdc[] = { 1, 1, -1, -1}; for (int i = 0; i < (curr.type == 0 ? 8 : 4); ++i) { int nr = curr.r + (curr.type == 0 ? kdr[i] : bdr[i]); int nc = curr.c + (curr.type == 0 ? kdc[i] : bdc[i]); if (!(0 <= nr && nr < row && 0 <= nc && nc < col)) continue; bool nType = isRed[nr][nc] ? !curr.type : curr.type; if (cost[nType][nr][nc] == -1) { cost[nType][nr][nc] = cost[curr.type][curr.r][curr.c] + 1; Q.push(Data(nType, nr, nc)); } } } cout << -1 << endl; } int main() { read(); work(); return 0; }