#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int DY[12] = {-2, -2, -1, -1, 1, 1, 2, 2, -1, -1, 1, 1}; const int DX[12] = {-1, 1, -2, 2, -2, 2, -1, 1, -1, 1, -1, 1}; const int KNIGHT = 0; const int BISHOP = 1; struct Node { int y; int x; int dist; int type; Node(int y = -1, int x = -1, int dist = -1, int type = -1) { this->y = y; this->x = x; this->dist = dist; this->type = type; } }; int main() { int H, W; cin >> H >> W; vector S; int sy, sx, gy, gx; for (int y = 0; y < H; ++y) { string row; cin >> row; S.push_back(row); for (int x = 0; x < W; ++x) { if (S[y][x] == 'S') { sy = y; sx = x; } if (S[y][x] == 'G') { gy = y; gx = x; } } } queue que; que.push(Node(sy, sx, 0, KNIGHT)); int visited[H][W][2]; memset(visited, -1, sizeof(visited)); while (not que.empty()) { Node node = que.front(); que.pop(); if (visited[node.y][node.x][node.type] != -1) continue; visited[node.y][node.x][node.type] = node.dist; // fprintf(stderr, "(%d, %d, %d, %d)\n", node.y, node.x, node.dist, node.type); if (node.type == KNIGHT) { for (int direct = 0; direct < 8; ++direct) { int ny = node.y + DY[direct]; int nx = node.x + DX[direct]; if (ny < 0 || H <= ny || nx < 0 || W <= nx) continue; if (S[ny][nx] == 'R') { que.push(Node(ny, nx, node.dist + 1, BISHOP)); } else { que.push(Node(ny, nx, node.dist + 1, KNIGHT)); } } } else { for (int direct = 8; direct < 12; ++direct) { int ny = node.y + DY[direct]; int nx = node.x + DX[direct]; if (ny < 0 || H <= ny || nx < 0 || W <= nx) continue; if (S[ny][nx] == 'R') { que.push(Node(ny, nx, node.dist + 1, KNIGHT)); } else { que.push(Node(ny, nx, node.dist + 1, BISHOP)); } } } } if (visited[gy][gx][KNIGHT] == -1 && visited[gy][gx][BISHOP] == -1) { cout << -1 << endl; } else if (visited[gy][gx][KNIGHT] == -1) { cout << visited[gy][gx][BISHOP] << endl; } else if (visited[gy][gx][BISHOP] == -1) { cout << visited[gy][gx][KNIGHT] << endl; } else { cout << min(visited[gy][gx][KNIGHT], visited[gy][gx][BISHOP]) << endl; } return 0; }