Topcoder SRM 525 div2 medium "DropCoins"

グリッドで表された長方形とその上に乗っているコインの状態と残すべきコインの数が与えられる．長方形の上のコインの状態を保持したまま上下左右に１つずつ動かせる．このとき長方形上から外れたコインはなくなる．この動作を用いて長方形上にあるコインの数を指定された数にしたいときの動作の回数の最小を求める．

上下左右にごっそり動くので，ある動作内で落ちない部分は長方形にしかならない．つまり，与えられた長方形に含まれる部分長方形の中にあるコインの数が指定されたコインの数であるかどうかを調べることで，ある動作後のコインの状態を表すことができるみたい．そして，ある部分長方形が定まると，その部分長方形にするための最小動作は一意に定まるようである．それは上に目一杯動かしてまた下に目一杯動かす．左右の時も同様にすることで「片方の端までの往復+もう片方の端までの往路」となる．往復を片方ずつ端までの動作の数で小さい方を選べば最小動作となり，最小動作の数が求められるらしい．

30^6でも十分間に合うようす．本番では自分は解けなかったがDFSっぽいのを最大ケースで落として30^6で失敗した．

public class DropCoins {

	public int getMinimum(String[] board, int K) {
		int n = board.length, m = board[0].length();
		char[][] cs = new char[n][];
		for (int i = 0; i < n; ++i) {
			cs[i] = board[i].toCharArray();
		}
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				for (int ii = i; ii < n; ++ii) {
					for (int jj = j; jj < m; ++jj) {
						int c = 0;
						for (int x = i; x <= ii; ++x) {
							for (int y = j; y <= jj; ++y) {
								if (cs[x][y] == 'o') {
									++c;
								}
							}
						}
						if (c == K) {
							int li = n - ii - 1, lj = m - jj - 1;
							result = Math.min(result,
									i + li + j + lj + Math.min(i, li) + Math.min(j, lj));
						}
					}
				}
			}
		}
		return result < Integer.MAX_VALUE ? result : -1;
	}
}