H 行 W 列の迷路が与えられます。各マスは次のいずれかです。
S : スタート（1 つだけ）G : ゴール（1 つだけ）. : 通れる道# : 壁（通れない）スタートから出発し、上下左右に隣り合うマスへ 1 歩ずつ移動します（壁のマスや迷路の外へは移動できません）。スタートからゴールまで移動するのに必要な最小の歩数を求めてください。ゴールにたどり着けない場合は -1 を出力してください。
S と G はそれぞれちょうど 1 つずつあります。入力は以下の形式で標準入力から与えられます。1 行目に H と W、続く H 行に迷路が与えられます。
H W (1 行目の迷路) (2 行目の迷路) ... (H 行目の迷路)
スタートからゴールまでの最小歩数を半角数字で出力してください。たどり着けない場合は -1 を出力してください。
| 入力 | 出力 |
|---|---|
3 3 S.. .#. ..G | 4 |
3 3 S.. ..# .#G | -1 |
ここから少し本格的なアルゴリズムです。最短歩数といえば幅優先探索（BFS）。基本情報でも頻出の超重要テーマで、ここを越えると一気にレベルアップできます。
最初は難しく感じても大丈夫。「キューに入れる → 取り出す → 隣を入れる」の流れを一度書き切れば、迷路だけでなく多くの問題に応用できる強力な武器になります。じっくり取り組む価値あり！
下のエディタにコードを書き、「コンパイル・実行」で試し、「提出」で全テスト採点します。言語は C / C++ / Java から選べます。全テスト合格でこの問題はクリア（👑）です。
本番の編集・コンパイル・実行・採点は Exercode 上で行います。このページは予習・練習用です（実行は Wandbox の実コンパイラを利用）。