7K12 blog

猫でも分かるアルゴリズム解説

ABC007 C - 幅優先探索

f:id:tkr987:20200620191638p:plain

f:id:tkr987:20200620191651p:plain

https://atcoder.jp/contests/abc007/submissions/14492447

  • 最短経路を記録するので更新してないグリッドだけ選んで移動していく

f:id:tkr987:20200620191822p:plain

BFSの基本問題。BFSは移動先座標をキューに入れて実現する。4方向に移動しながら、現在いる座標+1で移動先の座標を更新していく。ただし、移動先が更新済み座標と壁座標のときは更新せず、キューにも入れないようにする。最短経路なので、スタート地点だけ0で初期化し、それ以外の座標は十分大きな値で初期化しておくと実装が楽になる。