f:id:c_taquna:20200115005201p:plain

はじめに

本記事のテーマ

AtCoder Beginner Contest 151 D問題 - Maze Master の解き方について説明します。

問題を読み解いてみます。スタートを設定したら移動回数が最小になるようにゴールに移動する→つまり、スタートからゴールまで最短経路を通るということと考えられます。

スタートとゴールを任意に設定した時に移動回数は最大で何回になるか→つまり、スタートとゴールのすべての組み合わせについて、最も離れるように設定する

これをまとめると、

と言い換えられます。

与えられた迷路の通過可能なすべてのマスを対象に、各マスから最も遠い到達可能なマスまでの移動回数を求めます。その中で最も大きい移動回数となる値が今回の答えです。これはBFSを使用して、スタート地点の全探索をすることでもとめることができます。計算量はO((HW)²)なので、十分間に合います。

実装の全体は下記に乗せておきます。 github.com

過去の記事では、BFSの実装はスタートとゴールの座標情報を引数として渡していたので、スタートとゴールの組み合わせをfor文で実装していた(for文の4重構造)のですが、これはTLEしました。

そもそも、幅優先探索では、

と近い場所から確定していくので、BFSを最後まで処理して、その時の値を返せば自ずとスタートに対して最も遠いゴールまでの移動回数を求めることができます。つまり、スタート地点の全探索で、各スタートにおける最も遠いゴールまでの移動回数を求めて、さらにその中でも最大値を答えにすればOKです。