AtCoder AGC #004 : C - AND Grid

今回Cに手こずり過ぎて失敗。
http://agc004.contest.atcoder.jp/tasks/agc004_c

問題

H*Wのマス目がある。
ある連結マス群を赤く塗り、別の連結マス群を青く塗った。
両方で塗ったマスは紫色となる。

入力として紫色のマス群が与えられる。
そのようなマスの状態を生成できる、赤・青の塗り方の１例を答えよ。
なお、外周部は紫でないことが保証される。

解法

まず、全てのマスを、以下の条件を満たすように塗ることを考える。

• すべてのマスは赤か青のどちらかで塗られている。
• 外周部以外のマスには、隣接する４マスには赤・青が最低１個ある。

こうすると、後は入力に合わせ任意のマスを紫にする(連結関係を維持したまま、赤と青両方で塗る)ことができる。
回答を書いてしまうと、下記のように櫛を２つかみ合わせた形状にすると、上記条件を満たせる。

########  ........
#.#.#.#.  .#.#.#.#
#.#.#.#.  .#.#.#.#
#.#.#.#.  .#.#.#.#
#.#.#.#.  .#.#.#.#
#.#.#.#.  .#.#.#.#
........  ########

int H,W;
string S[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(x,W) S[0][x]='$', S[H-1][x]='&';
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') S[y][x]="$&"[x%2];
	
	FOR(y,H) {
		FOR(x,W) cout<<((S[y][x]=='&')?'.':'#');
		cout<<endl;
	}
	cout<<endl;
	FOR(y,H) {
		FOR(x,W) cout<<((S[y][x]=='$')?'.':'#');
		cout<<endl;
	}
	
	
}

まとめ

よくこんな問題思いつくな。