SRM525 Div1 300

問題

1x1のセルによって構成される長方形がある。各セルには、何もないか、コインが1枚のっている。
各ターンに、上下左右のどれか1方向に全てのコインを1セル分動かすことができる。
もし長方形の外側にでてしまったコインは消える。
正確にKコインだけを残すために必要な最小ターン数を答えよ。不可能ならば-1を返す。

1<=w,h<=30
1<=K<=900

考え方

上下左右にすべてのコインを動かすので最終的に残るコインは長方形の内部にできる小さな長方形内のコインということになる。
もし、この小さな長方形が決定し、その内部のコインがK枚ならば、その長方形が残るように動かせばよい。
その長方形が残るように動かす最小ターン数を考える。
上下方向を考えると、マスが小さいほうに動かしてから逆方向に動かすのが最小になる(上→下(元の位置)→下か下→上(元の位置)→上)。
左右方向も同様なので、その合計ターン数で一番小さいものを返せばよい。