TopCoder SRM 525 Div1 Easy DropCoins

問題

nxmの板がある。
それぞれのマスは空白'.'またはコインが1枚載っている'o'

板を1つ横または縦に動かす操作が出来る。
操作の結果板からはみでたコインは落ちてなくなる。
操作を繰り返して板に載っているコインの数をちょうどk枚にしたい。

そのような状態にいたるための操作の最低回数を求めよ。
不可能な場合は-1を返せ。

制約条件

n,m≦30

方針

残す長方形を一つ決める。
(x1,y1),(x2,y2)を残したとすると、その長方形だけを残すために必要な操作は、
min(x1,w-x2)*2+max(x1,w-x2)+min(y1,h-y2)*2+max(y2,h-y2)回

これを全通り試せばいい。
長方形内部のコインの個数は前処理をしておくことでO(1)で求められるが、
別に前処理をしなくても間に合う。

ソースコード

int sum[31][31];
int calc(int y1,int x1,int y2,int x2){
	return sum[y2][x2]-sum[y2][x1]-sum[y1][x2]+sum[y1][x1];
}
int calc2(int a,int b){
	return min(a,b)*2+max(a,b);
}
class DropCoins {
	public:
	int getMinimum(vector <string> board, int K) 
	{
		int h=board.size(), w=board[0].size();
		memset(sum,0,sizeof(sum));
		rep(i,h)rep(j,w)sum[i+1][j+1]=(board[i][j]=='o')+sum[i+1][j]+sum[i][j+1]-sum[i][j];
		
		int ans=inf;
		rep(i,h)rep(j,w)for(int k=i;k<=h;k++)for(int l=j;l<=w;l++){
			if(calc(i,j,k,l)==K)ans=min(ans,calc2(i,h-k)+calc2(j,w-l));
		}
		return ans==inf?-1:ans;
	}
};