第10回日本情報オリンピック予選 E チーズ 解説
問題文
https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e
・盤面上のチェックポイント1~nのすべてを番号順に通過するときの移動回数の最小を求める。
・Xで記されているのは障害物で、ここを通ることはできない。
ACコード
https://atcoder.jp/contests/joi2011yo/submissions/4819003
解説
・pair型の配列を用意する。配列の添え字0にはSの座標、それ以降はチェックポイントnの座標を格納する。
・for文を回し、その中でスタートする座標と次のチェックポイントの座標を更新する。
・スタートの座標から次のチェックポイントまでの最短経路を幅優先探索により求める。
解いた感想
体感難易度:☆4
・初めて幅優先探索を使った問題を解いた(バグらせまくったため最終的にはACコードの写経に近くなってしまった)
・配列に格納される座標はx,yではなくy,xの順番になっていることに注意する。
・基本的な原理は理解できたつもりなので実装に慣れる。