No.367 ナイトの転身

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 114
作問者 : 🍡yurahuna🍡yurahuna / テスター : 紙ぺーぱー紙ぺーぱー
3 ProblemId : 996 / 出題時の順位表
問題文最終更新日: 2016-04-27 05:43:45

問題文

あなたはチェスの駒を用いたゲームに取り組んでいます。
このゲームは、$H$行$W$列のチェス盤上で、駒をスタート地点のマスからゴール地点のマスまで移動させるとクリアとなります。
ゲームの最初には、スタート地点に駒が置かれており、このとき駒はナイトです。
あなたはこの駒を動かしてゲームを進めますが、
チェス盤のいくつかのマスは赤いマスで、
赤いマスに止まると駒がナイトから「ミニビショップ」(後述)に変わります。
同様に、駒がミニビショップのときに赤いマスに止まると駒はナイトに変わります。
すなわち、赤いマスに関するルールは以下のように記述されます。
(ここで、駒を1度動かすことを「1手」と数えることにします。)

  • 「$k$手目の移動を開始する時点で駒がナイト」かつ「$k$手目の移動先のマスが赤いマス」であれば、
    $ k + 1 $ 手目から 次に赤いマスに止まるまでの間、駒はミニビショップとなる。
  • 「$k$手目の移動を開始する時点で駒がミニビショップ」かつ「$k$手目の移動先のマスが赤いマス」であれば、
    $ k + 1 $ 手目から 次に赤いマスに止まるまでの間、駒はナイトとなる。
ナイトとミニビショップの駒の利きは以下の通りです。
(以下の説明では、$i$ 行 $j$ 列目のマスを$(i, j)$と表します。)

  • ナイトが位置 $(i, j)$ にいるとき、次に移動できる位置は $ (i \pm 1, j \pm 2), (i \pm 2, j \pm 1) $ である。
  • ミニビショップが位置 $(i, j)$ にいるとき、次に移動できる位置は $ (i \pm 1, j \pm 1) $ である。
  • ただし、ナイトもミニビショップもチェス盤の外に出ることはできない。
図で表すと、ナイトの利き(左)とミニビショップの利き(右)は以下のようになります。
Nがナイト(kNight)、Bがミニビショップ(mini-Bishop)の位置を表し、丸の書かれたマスが移動できるマスを表します。



さて、あなたは最短何手でこのゲームをクリアすることができるでしょうか?

入力

$H$ $W$
$s_1$
$s_2$
.
.
.
$s_H$

  • 1行目にはチェス盤の行数 $H$ , 列数 $W$ $ (1 \leq H \leq 500, 1 \leq W \leq 500) $ がスペース区切りの整数で与えられる。
  • 2行目から $ H + 1 $ 行目には、チェス盤の各マスの情報が与えられる。 $i + 1$ 行目の 文字列 $s_i$ の $j$ 文字目 が $i$ 行 $j$ 列目のマスの情報を表す。
    各文字の意味は以下の通りである。
    • 'S' : スタート地点
    • 'G' : ゴール地点
    • 'R' : 赤いマス
    • '.' : その他のマス
    これら以外の文字は $s_i (1 \leq i \leq H)$ には存在せず、'S'および'G'はちょうど1つずつ存在する。

出力

駒をスタート地点からゴール地点まで動かすのにかかる最短手数を、1行で出力してください。
駒がゴール地点に到達不可能な場合には-1を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 4
...G
.RR.
.RR.
S...
出力
3

例えば(4, 1) -> (2, 2) -> (3, 3) -> (1, 4) と移動すると最短手数でクリアできます。
このとき、駒は ナイト -> ミニビショップ -> ナイト と変化します。

サンプル2
入力
3 4
...G
....
S...
出力
3

この例ではチェス盤に赤いマスはありません。 例えば (3, 1) -> (1, 2) -> (3, 3) -> (1, 4) と移動すると最短手数でクリアできます。

サンプル3
入力
3 3
.R.
RGR
SR.
出力
-1

この例では、駒はゴール地点に到達することができません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。