UnKoder #02 : Binary Matrix

似たような問題をSRMで見たことあったような気がするけど、気のせいかな。
https://www.hackerrank.com/contests/unkoder-02/challenges/binary-matrix

問題

N行M列の行列がある。
各要素は、0か1か未定である。
未定の箇所は0か1で埋めることができる。

この行列の美しさは、「行全体が同じ値であるような行の数」と「列全体が同じ値であるような列の数」の和である。
未定の箇所を適切に埋めた場合、得られる美しさの最大値を求めよ。

解法

行全体が同じ値になるようにした結果、0の行と1の行が存在してしまうと、列全体が同じ値にはなりえない。
行と列でそれぞれ美しさを稼ぐためには、いずれも01が同じ値である必要がある。

よって未定の箇所を埋める際取れる戦略は以下の4通りであり、それぞれの美しさの最大値を求めればよい。

• 未定の箇所を全部0で埋める。
• 未定の箇所を全部1で埋める。
• 未定の箇所を出来るだけ行全体が同じ値になるように埋める。
• 未定の箇所を出来るだけ列全体が同じ値になるように埋める。

int H,W;
string S[51];
string T[51];

int num() {
	int x,y,ret=0;
	FOR(y,H) {
		int ok=1;
		FOR(x,W-1) if(T[y][x]!=T[y][x+1]) ok=0;
		ret+=ok;
	}
	FOR(x,W) {
		int ok=1;
		FOR(y,H-1) if(T[y][x]!=T[y+1][x]) ok=0;
		ret+=ok;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y,ret=0;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	// all zero
	FOR(y,H) {
		T[y]=S[y];
		FOR(x,W) if(T[y][x]=='?') T[y][x]='0';
	}
	ret=max(ret,num());
	
	// all one
	FOR(y,H) {
		T[y]=S[y];
		FOR(x,W) if(T[y][x]=='?') T[y][x]='1';
	}
	ret=max(ret,num());
	// col
	FOR(y,H) T[y]=S[y];
	FOR(x,W) {
		char hoge='0';
		FOR(y,H) if(T[y][x]!='?') hoge=T[y][x];
		FOR(y,H) if(T[y][x]=='?') T[y][x]=hoge;
	}
	ret=max(ret,num());
	// row
	FOR(y,H) {
		T[y]=S[y];
		char hoge='0';
		FOR(x,W) if(T[y][x]!='?') hoge=T[y][x];
		FOR(x,W) if(T[y][x]=='?') T[y][x]=hoge;
	}
	ret=max(ret,num());
	
	cout<<ret<<endl;
}

まとめ

最小カットに持ち込んでも解けるそうだけど、そっちの方が難しそう。