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; } };