スタートからゴールまで最短距離で辿り着く(幅優先探索)

問題

C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder

ソースコード

解説

問題文に書いてある通り、キューを用いた幅優先探索によって最短経路を算出する。

ポイント１

幅優先探索の流れ

初めにキューに入れるノード(start)の初期化
startを訪問済みとする
while キューが空になるまで {
    キューからノードpointを取り出す。
    pointの子ノードchildrenを取得(pointから進むことのできるノード郡)
    for newPoint: children {  //それぞれの子に対して
         newPointに対して行いたい処理
         newPointを訪問済みとする
         キューにnewPointを追加
    }
} 

なぜ幅優先が使えるか

今回の問題は最短経路を探す問題であり、且つ迷路は４方向のどれかにしか進むことができない。幅優先探索は、親ノードに隣接している子ノードを順番に探索するので、スタート地点からゴールまで順番に探索することができる。

ポイント２

４方向チェックの場合は以下のようにvxとvyを用意することで綺麗にチェックすることができる。

int[] vx = { 0, 1, 0, -1 };
int[] vy = { 1, 0, -1, 0 };

for (int i = 0; i < 4; i++) {
    int nx = point.x + vx[i];
    int ny = point.y + vy[i];