第21回日本情報オリンピック　二次予選

2022年2月5日
情報オリンピック日本委員会

解説

解説担当：平木康傑

小課題については省略し，満点を得られる解法について解説する．

この問題のように探索が求められる問題では，「幅優先探索」と「深さ優先探索」がしばしば有効である．特に，今回は最短の手数を求める必要がある状況なので，幅優先探索を用いるのが妥当である．なお，深さ優先探索を用いると小課題 1, 2, 3 は通るが，満点がとれるほど高速ではない．

また，2 次元グリッドをグラフとみなして，最短経路問題に落とし込むことも考えられる．この場合は幅優先探索のほかに，Dijkstra 法を適用しても解ける．

C++ の解答例は幅優先探索による方針を採っている．`std::queue` を用いて実装しているが，ほかにも様々な方法がある．

Python の解答例は Dijkstra 法による方針を採っている．3-16 行目ではグリッドをグラフに落とし込んでおり，17-24 行目では Dijkstra 法を実行している．