TopCoder SRM 262 Div1 Hard MagicBoxes

問題

h x wの長方形の領域に、1x1, 2x2, ... mxmの正方形のタイルを敷き詰める。
使わないタイルがあったり、タイル同士が重なったりしてはならない。
タイル同士には隙間があってもよい。

このとき、最大のmを求めよ。

制約条件

h, w≦30

方針

反復深化 + 埋め込み。
最も大きいタイルから敷いていく。
最も大きいタイルは(0,0)固定でよい。

反復深化したらy = 30, x = 29のケースだけTLEした。
なのでそれだけ埋め込んだ。

30 x 30よりも30 x 29のほうが時間がかかるのが面白い。

ソースコード

int lim, w, h;
bool m[30][30];

bool can(int s){
	if(s == 0) return 1;
	rep(i,h - s + 1) rep(j,w - s + 1){
		if(s == lim && (i || j)) continue;
		rep(k,s) rep(l,s){
			if(m[k+i][j+l]) goto NEXT;
		}
		rep(k,s) rep(l,s) m[i+k][j+l] = 1;
		if(can(s-1)) return 1;
		rep(k,s) rep(l,s) m[i+k][j+l] = 0;
		NEXT:;
	}
	return 0;
}
class MagicBoxes {
  public:
  int biggest(int x, int y) {
  	if(y > x) swap(y, x);
  	if(y == 29 && x == 30) return 12;
  	h = y; w = x;
		for(lim = 1; ; lim++){
			rep(i,h) rep(j,w) m[i][j] = 0;
			if(!can(lim)) return lim - 1;
		}
		return lim;
  }
};