yukicoder : No.226 0-1パズル

面白かったです。
http://yukicoder.me/problems/600

問題

H*Wのグリッドがあり、一部セルが0か1が埋められている。

このグリッド中で2*2の領域に着目したとき、0と1が２セルずつになるよう空セルを0と1で埋めたい。
条件を満たすグリッドの埋め方は何通りあるか。

解法

Writer解とは少し違うかな。

考察していくと、縦方向と横方向の少なくとも片方は0と1が交互に現れる。
よって、それぞれが01交互になるパターンをDPで列挙しよう。

例えば縦方向に01が交互になる場合、最上位行が0の場合と1の場合を考え、既存のセルの値と矛盾しないケースを数え上げていけば良い。

以下のコードでは、縦方向に01が交互になる場合だけを求め、その後グリッドを90度回転させて同じ処理を繰り返している。
さらに、この手法では全体が完全に市松模様になるケースを二重カウントしてしまうので、そこは最後に減算している。

int H,W;
string S[1010],T[1010];
ll mo=1000000007;
ll dp[101][2];

ll pat() {
	int i,j,x,y;
	
	ZERO(dp);
	dp[0][0]=1;
	FOR(x,W) {
		FOR(i,2) FOR(j,2) {
			int ng=0;
			FOR(y,H) if(S[y][x]!='?' && S[y][x]!='0'+(i+j+y)%2) ng++;
			if(ng==0) (dp[x+1][(i+j)%2]+=dp[x][i])%=mo;
		}
	}
	return dp[W][0]+dp[W][1];
}

ll perf() {
	int ok1=1,ok2=1;
	int i,j,k,l,r,x,y; string s;
	
	FOR(y,H) FOR(x,W) if(S[y][x]!='?') {
		if((S[y][x]-'0')!=((y+x)%2)) ok1=0;
		if((S[y][x]-'0')==((y+x)%2)) ok2=0;
	}
	return ok1+ok2;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	// subtract perfect ichimatsu
	ll ret=mo-perf();
	FOR(i,2) {
		ret += pat();
		
		// rotate
		FOR(x,W) FOR(y,H) T[x]+=S[y][x];
		FOR(x,W) S[x]=T[x];
		swap(H,W);
	}
	
	cout<<ret%mo<<endl;