ABC 151 D - Maze Master - sky’s 雑記

初手の方針

蟻本のDFS/BFSで迷路探索問題は見ていてアルゴリズムはわかっていたが実装力が足りなくて手が出せなかった。

幅優先探索について

幅優先探索の実装において抑えておくポイントみたいなものを記しておく。

以下のような迷路を例にとって、

...
...
...

マスに番号をつける。

1,2,3
4,5,6
7,8,9

キュー

幅優先探索を実現するデータ構造、cppではqueueで実現する。先入れ先出しなので{1} -> {2,4} -> {4,3,5} -> {3,5,7} -> {5,7,6} -> {7,6,8} -> {8,9} -> {} といった具合に近いところから順に探索していく。

ベクター

各マスが訪問済みかどうかを管理するデータ構造、boolやintで初期値を設定し訪問する際に初期値=未訪問であれば値を更新する。intでもたせる場合は同時に初期位置から移動に必要な距離も求めることができる。初期値-1とすると最終的にベクターは以下のようになる。 {-1,-1,-1,-1,-1,-1,-1,-1,-1} -> {0,1,2,1,2,3,2,3,4}