原案：kuronosu1024

元の問題

$H$ 行 $W$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。
各マスの状態は $S_{i,j}$ で表され、$S_{i,j}$ が # のときそのマスは壁、. のときそのマスは壁がない、S のときは馬がいる、G のときはゴールです。

馬がゴールにたどり着くまでの最小移動回数を出力してください。ただし馬がゴールにたどり着けない場合は -1 を出力してください

馬の移動方法について
馬のいる場所を $(i,j)$ とします。
移動先がマス目の範囲内であるとき、馬は以下のいづれかのマスに移動することができます。

• $(i+2,j-1)$
• $(i+2,j+1)$
• $(i+1,j-2)$
• $(i+1,j+2)$
• $(i-1,j-2)$
• $(i-1,j+2)$
• $(i-2,j-1)$
• $(i-2,j+1)$

想定エスパー法

サンプル全体から S のマスから G のマスにたどり着くまでの最短手数の問題であるとエスパーします。
サンプル3から移動方法は四近傍や八近傍ではなく複数マスを飛ばしての移動であるとエスパーします。
サンプル全体から移動方法がチェスのナイトと同じ移動方法であるとエスパーします。

またサンプル1,2,3で盤面が8×8マスになっているところと $S$ の位置からもチェスのナイトであることをエスパーできます。

解法

この問題は移動方法を元の問題のようにした BFS で解くことができます。