ABC020 C - 壁抜け
解法
スタート地点から座標へ向かうルートのうち、黒のマスを合計回、白のマスを回通るようなものが存在するかどうか
とします。すると、これは現在の座標と、通った黒と白のマスの個数をセットで記録しつつスタート地点から順番に幅優先探索を行うことで、この配列を完成させることができます。
あとは、ゴールの座標についてのこの配列の情報をもとに、答えを求めることができます。
スタートからゴールに向かうまでに、黒いマスを回、白いマスを回通ったとするとき、黒マスを通る秒数の最大値は次のようになります。
ただし、切り捨てです。
つまり、この式が最大となるようなの組み合わせを探せば答えとなります。
ので、がtrueとなるようなの組み合わせの中で、上の式で計算した値の最大値を求めれば、この問題が解けます。