TopCoder SRM 553 Div1 Medium TwoConvexShapes

やることは割と明白だけどかなりメンドイ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11492

問題

N*Mの2次元グリッドがある。
各セルは白か黒かまだ色が塗られていないのいずれかである。

このグリッドを以下のように塗る塗り分け方は何通りあるか。

• グリッド中に白セルがあるならば：
  • 全ての白セル同士は隣接セルで連結している。
  • 連結してできる領域は凸である(凸の厳密な定義は問題文参照)
• グリッド中に黒セルがあるならば：
  • 全ての黒セル同士は隣接セルで連結している。
  • 連結してできる領域は凸である

解法

4つの角に注目すると、問題文を満たす塗り方の必要条件は下記のいずれかである。

1. 全セルが白で、当然角もすべて白
2. 全セルが黒で、当然角もすべて黒
3. 4つの角のうち1つが白で、3つが黒
4. 4つの角のうち3つが白で、1つが黒
5. 4つの角のうち(互いに対角ではない)2つが白で、2つが黒

最初の2つは明確なので、残り3つをDPで処理していく。
1つの角だけ色が異なるパターンは、どの角の色を異なるようにするか考えるのが面倒なので、異なるのは左上に固定し、グリッド全体を回転するのが楽。

ll mo=1000000007;

class TwoConvexShapes {
	public:
	vector<string> G,G2;
	
	ll dodo(char tar,int type) {
		int H=G.size(),W=G[0].size();
		int y,x,z;
		char op='B'+'W'-tar;
		
		int mat[53][53];
		ll dp[53][53][2][3];
		ZERO(mat);
		ZERO(dp);
		
		if(G[0][W-1]==tar) return 0;
		
		FOR(y,G.size()) {
			int t=1;
			
			mat[y][0]=1;
			FOR(x,W) {
				if(t==1) {
					if(G[y][x]==op) t=0;
					else {
						if(G[y][x]==tar) {
							z=x;
							while(z>=0 && mat[y][z]) mat[y][z--]=0;
						}
						mat[y][x+1]=1;
					}
				}
				else {
					if(G[y][x]==tar) return 0;
				}
			}
			
			if(y==0) {
				for(x=1;x<=W-1;x++) dp[0][x][0][0]=dp[0][x][0][1]=dp[0][x][0][2]=mat[y][x];
			}
			else {
				FOR(x,W) if(mat[y][x]) {
					for(z=x+1;z<W;z++) dp[y][x][1][0]+=dp[y-1][z][0][0]+dp[y-1][z][1][0];
					FOR(z,x) dp[y][x][1][1]+=dp[y-1][z][0][1]+dp[y-1][z][1][1];
					
					dp[y][x][0][0] += dp[y-1][x][0][0];
					dp[y][x][1][0] += dp[y-1][x][1][0];
					dp[y][x][0][1] += dp[y-1][x][0][1];
					dp[y][x][1][1] += dp[y-1][x][1][1];
					dp[y][x][0][2] += dp[y-1][x][0][2];
					dp[y][x][0][0] %= mo;
					dp[y][x][1][0] %= mo;
					dp[y][x][0][1] %= mo;
					dp[y][x][1][1] %= mo;
					dp[y][x][0][2] %= mo;
				}
			}
		}
		
		ll ret=0;
		if(type==0) {
			ret=dp[H-1][0][1][0];
		}
		else {
			for(x=1;x<W;x++) ret+=dp[H-1][x][1][0]+dp[H-1][x][1][1]+dp[H-1][x][0][2];
		}
		return ret%mo;
	}
	
	int countWays(vector <string> grid) {
		ll ret=0;
		int i,j,k,x,y;
		string S;
		
		G=grid;
		
		// allsame
		FOR(y,G.size()) S+=G[y];
		ret=(count(S.begin(),S.end(),'B')==0)+(count(S.begin(),S.end(),'W')==0);
		
		FOR(i,4) {
			ret+=dodo('B',0);
			ret+=dodo('W',0);
			ret+=dodo('B',1);
			// rot
			grid=G;
			G.clear();
			FOR(y,grid[0].size()) G.push_back(string(grid.size(),'*'));
			FOR(y,grid.size()) FOR(x,grid[0].size()) G[grid[0].size()-1-x][y]=grid[y][x];
		}
		
		return ret%mo;
	}
}

まとめ

とにかくめんどくさい問題。
他の解法も多少短いものはあっても、極端に短い解法はなかった。