ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC020 C - 壁抜け

問題
提出コード

解法

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