幅優先探索法 :BFS

こんにちは。Arkです。

今日は初めてBFSに触れたので記事にしました。

今回解いた問題は

• ABC088-D Grid Repainting

https://atcoder.jp/contests/abc088/tasks/abc088_d

です。幅優先探索というものの存在を知ってはいましたが、全く実装方法が分からなかったので蟻本(通称: プログラミングコンテストチャレンジブック)を参考にしながら書きました。ちなみに今日買いました。高かったです(´;ω;｀)

以下が僕のコードです。コメント盛りだくさんです。伝わってくれると嬉しいです。

https://atcoder.jp/contests/abc088/submissions/5437847

加えて、28行目のwhile文以下の説明を僕なりに考察しながら書きます。間違ってたらコメントをください！！

まず、p=que.front() で、queに入っている一番最初のものを参照します。次に、参照したものは que.pop() で捨てます。この操作がないと一度探索したことのある座標をもう一度参照することになってしまい、無限ループになってしまいます。

次に、指定した座標の前後左右 (next_x, next_y) を見ます。その時、最初に与えられている迷路をはみ出して探索することがないように、(1<=next_x<=W) かつ (1<=next_y<=H) の条件を付けます。また、この問題では  ' . ' のマスのみ移動可能なのでこのあたりも条件に付けます。加えて、次に進む点が未訪か既訪かを示すフラグ (未訪ならINF) を見て、未訪なら更新し、次のループでその点を起点とできるようにque.push()します。そして、一マス動いたのでdistanceを+1します。

最後にdist[W][H]を出力するんですが、スタートからゴールまで行くことができれば最短距離が格納されていますし、ゴールできない場合は最初に入力したINFが入っています。

こんな感じで読み解きながら実装しました。結構自己満な記事ですが、自分が振り返ることができるし、説明するにあたって自分の穴をなくすことができるのでこれからも書いていきたいと思います。暇があれば、たまに目を通してくれると嬉しいです。

精進頑張ります！！！