TopCoderOpen 2013 Round1B Medium EllysFigurines

さてMedium。
Div2 Mediumより難しく、Div1 Mediumよりは簡単かな。
http://community.topcoder.com/stat?c=problem_statement&pm=12447

問題

マス目上にいくつか人形が置いてある。
プレイヤーは１手で連続するR行または連続するC列に並ぶ人形をすべて取り除くことができる。
マス目上のすべての人形を取り除く最少手数を答える。

解答

すでに取り除いた列および行をビットマスクで持っておく。
まだ残ってる人形がいたら、その人形を消すような列または行の消し方を選び、ビットマスクを更新して再帰的に人形がなくなるまで処理を行う。

map<int,int> memo;

class EllysFigurines {
	public:
	int W,H,R,C;
	vector<string> B;
	int calc(int ymask, int xmask) {
		int y,x,tx=-1,ty=-1,m;
		
		if(memo.find((ymask<<15)+xmask)!=memo.end())
			return memo[(ymask<<15)+xmask];
		
		FOR(y,H) {
			if(ymask & (1<<y)) continue;
			FOR(x,W) {
				if(xmask & (1<<x)) continue;
				if(B[y][x]=='.') continue;
				ty=y; tx=x;
				goto end;
			}
		}
		end:
		m=0;
		if(tx!=-1) {
			m=100;
			//yoko
			for(y=max(0,ty-(R-1));y<=ty;y++) {
				m = min(m, calc( (ymask | (((1<<R)-1)<<y)) & ((1<<H)-1),xmask));
			}
			//tate
			for(x=max(0,tx-(C-1));x<=tx;x++) {
				m = min(m, calc(ymask, (xmask | (((1<<C)-1)<<x)) & ((1<<W)-1)));
			}
			m++;
		}
		return memo[(ymask<<15)+xmask]=m;
	}
	
	int getMoves(vector <string> board, int R, int C) {
		B=board;
		H=B.size();
		W=B[0].size();
		this->R=R;
		this->C=C;
		
		int x,y;
		memo.clear();
		return (int)calc(0,0);
	}

};

まとめ

最初TLEになるかなと思ったけど、列や行の最大値が割と小さいので何とかクリア。