/* -*- coding: utf-8 -*- * * 367.cc: No.367 ナイトの転身 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 500; const int MAX_W = 500; const int INF = 1 << 30; const int dns[2] = {8, 4}; const int dxs[2][8] = { {2, 1, -1, -2, -2, -1, 1, 2}, {1, -1, -1, 1} }; const int dys[2][8] = { {-1, -2, -2, -1, 1, 2, 2, 1}, {-1, -1, 1, 1} }; /* typedef */ struct Stat { int x, y, k; Stat() {} Stat(int _x, int _y, int _k): x(_x), y(_y), k(_k) {} }; /* global variables */ string flds[MAX_H]; int dists[MAX_H][MAX_W][2]; /* subroutines */ /* main */ int main() { int h, w; cin >> h >> w; int sx, sy, gx, gy; for (int y = 0; y < h; y++) { cin >> flds[y]; for (int x = 0; x < w; x++) { switch (flds[y][x]) { case 'S': sx = x; sy = y; flds[y][x] = '.'; break; case 'G': gx = x; gy = y; flds[y][x] = '.'; break; } } } for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) for (int k = 0; k < 2; k++) dists[y][x][k] = INF; dists[sy][sx][0] = 0; queue q; q.push(Stat(sx, sy, 0)); int mind = INF; while (! q.empty()) { Stat u = q.front(); q.pop(); if (u.x == gx && u.y == gy) { mind = dists[u.y][u.x][u.k]; break; } int vd = dists[u.y][u.x][u.k] + 1; int vk = (flds[u.y][u.x] == 'R') ? (u.k ^ 1) : u.k; for (int di = 0; di < dns[vk]; di++) { int vx = u.x + dxs[vk][di], vy = u.y + dys[vk][di]; if (vx >= 0 && vx < w && vy >= 0 && vy < h && dists[vy][vx][vk] > vd) { dists[vy][vx][vk] = vd; q.push(Stat(vx, vy, vk)); } } } printf("%d\n", (mind >= INF) ? -1 : mind); return 0; }