TopCoder SRM 553 Div1 Medium TwoConvexShapes

問題

HxWのグリッドを'B'または'W'の色で塗る。
既に色が塗られているところはB, Wの文字が書かれていて、
そうでないマスには'?'が書かれている。

このグリッドの?のマスを全てBまたはWの色で塗り、以下の条件を満たすようにしたい。
全ての同色のマスは、連結で、凸である。
すなわち、同じ列または行に二つの同色のマスがあった場合、
その間のマスは全て同じ色で塗られている。

条件を満たす塗り方は何通りあるか、求めよ。

制約条件

H, W≦50

方針

条件を満たす塗り方というのは結局、一色が階段状になっている塗り方である。
階段状になっている塗り方の場合の数は、動的計画法により求まる。

階段が四隅のどこになるかが４通りありうるので、回転して全部数える。
このとき、全部のマスが白、または黒である状態は4回数えているので3回分引く。
また、白と黒のマスのかたまりが、ひとつの直線で分割される場合も2度ずつ数えているので、1回分引く。

これで答えが出る。

ソースコード

const int mod = (int)1e9 + 7;
vector<string> rot(vector<string> &g){
	int h = g.size(), w = g[0].size();
	vector<string> res(w, string(h, ' '));
	rep(i, h) rep(j, w) res[j][h - i - 1] = g[i][j];
	return res;
}
ll calc(const vector<string> &g){
	int h = g.size(), w = g[0].size();
	static ll dp[51][51];
	
	memset(dp, 0, sizeof(dp));
	
	dp[0][0] = 1;
	rep(i, h){
		int mxb = -1, mnw = w;
		rep(j, w){
			if(g[i][j] == 'B') mxb = j;
			if(g[i][j] == 'W') mnw = min(mnw, j);
		}
		if(mxb > mnw) break;
		rep(j, w + 1) if(dp[i][j]){
			for(int k = max(j, mxb + 1); k <= min(mnw, w); k++){
				(dp[i + 1][k] += dp[i][j]) %= mod;
			}
		}
	}
	ll res = 0;
	rep(i, w + 1) res += dp[h][i];
	return res;
}
ll calc2(const vector<string> &g){
	int h = g.size(), w = g[0].size();
	ll res = 0;
	for(int i = 1; i < h; i++){
		rep(j, w) if(g[i - 1][j] == 'W') goto END;
		for(int j = i; j < h; j++) rep(k, w) if(g[j][k] == 'B') goto FAIL;
		res++;
		FAIL:;
	}
	END:
	return res;
}

class TwoConvexShapes {
	public:
	int countWays(vector <string> grid) {
		ll ans = 0;
		rep(i, 4){
			ans += calc(grid);
			ans -= calc2(grid);
			grid = rot(grid);
		}
		int white = 1, black = 1;
		rep(i, grid.size()) rep(j, grid[0].size()){
			if(grid[i][j] == 'B') white = 0;
			if(grid[i][j] == 'W') black = 0;
		}
		ans -= white * 3 + black * 3;
		return (ans + mod) % mod;
	}
};