TopCoder SRM 485 Div1 Medium RectangleAvoidingColoring

問題

'W','B'または'?'からなるhxwのグリッドが与えられる。
'?'には'W'または'B'を任意に入れることが出来る。
以下の条件を満たすグリッドは何通りあるか、求めよ。

  • グリッドからどのように長方形(x1,y1),(x1,y2),(x2,y1),(x2,y2)を選んでもこの頂点が同じ色にならない。

制約条件

h,w≦50

方針

実は5x5以上のグリッドで条件を満たすものは存在しない。
なので、幅は4以下としてよく、動的計画法による数え上げができる。


たとえば白の頂点からなる長方形ができるときは、
ひとつの行の中に白がa番目とb番目にあり、
もう一つ別の行の中にもa番目とb番目に白がある。


(a,b)という数字のペアが異なる行で二度出てきたら、長方形が出来るということである。
なので、白、黒の色ごとに、今までに出てきた数字のペアを全部覚えておけばよい。


幅は4以下なので、ペアの数は4C3=6通り。一行あたり、2^6 * 2^6 = 4096通りの状態数になる。

ソースコード

ll dp[51][1<<6][1<<6];

class RectangleAvoidingColoring {
	public:
	long long count(vector <string> board) 
	{
		int h=board.size(),w=board[0].size();
		if(h<w){
			vs v(w,string(h,' '));
			rep(i,h)rep(j,w)v[w-j-1][i]=board[i][j];
			return count(v);
		}
		if(w>4)return 0;
		
		memset(dp,0,sizeof(dp));
		dp[0][0][0]=1;
		int n=w*(w-1)/2;
		rep(i,h)rep(a,1<<n)rep(b,1<<n)if(dp[i][a][b]){
			rep(mask,1<<w){
				int cnt=0, na=a, nb=b;
				rep(j,w)if(board[i][j]=='B'&&!(mask&1<<j))goto FAIL;
				rep(j,w)if(board[i][j]=='W'&&(mask&1<<j))goto FAIL;
				
				rep(j,w)rep(k,j){
					if((mask&1<<j)&&(mask&1<<k)){
						if(a&1<<cnt)goto FAIL;
						na|=1<<cnt;
					}
					if(!(mask&1<<j)&&!(mask&1<<k)){
						if(b&1<<cnt)goto FAIL;
						nb|=1<<cnt;
					}
					cnt++;
				}
				dp[i+1][na][nb]+=dp[i][a][b];
				FAIL:;
			}
		}
		ll ans=0;
		rep(i,1<<n)rep(j,1<<n)ans+=dp[h][i][j];
		return ans;
	}
};