UnKoder #07 : Grid Coloring

Bより簡単だった。
https://www.hackerrank.com/contests/unkoder-07/challenges/grid-coloring

問題

白マスと黒マスで構成されるグリッドが与えられる。
このうち全ての白マスを赤と青で塗り分けたい。
ただし、赤マス同士、青マス同士が隣接してはならない。

赤マスは最大何個塗れるか。

解法

赤マス同士、青マス同士が隣接できないので、これらは市松模様状に塗るしかない。

よって、白マスの各連結成分ごとに、(列+行)のパリティ毎のマスの数を数え上げ、多い方に赤を割り当てていけば良い。

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

pair<int,int> dfs(int cy,int cx) {
	pair<int,int> p=make_pair(0,0);
	if((cy+cx)&1) p.first++;
	else p.second++;
	S[cy][cx]='#';
	int i;
	FOR(i,4) {
		int dd[]={1,0,-1,0};
		int ty=cy+dd[i],tx=cx+dd[i^1];
		if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
		if(S[ty][tx]=='#') continue;
		auto p2=dfs(ty,tx);
		p.first+=p2.first;
		p.second+=p2.second;
	}
	return p;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') {
		pair<int,int> p=dfs(y,x);
		ret += max(p.first,p.second);
	}
	cout<<ret<<endl;
	
}

まとめ

こっちがBでもいいと思うんだけどな。