はまやんはまやんはまやん

hamayanhamayan's blog

AND Grid [AGC 004 : C]

問題

http://agc004.contest.atcoder.jp/tasks/agc004_c

縦H横Wの透明な方眼紙が2つある。
片方は赤色で、もう片方は青色で、どちらも連結な状態で塗られている。
これら2つの重ね合わせるとどちらも塗られている所が紫色になる。
重ねあわせて紫色になっているものが与えられるので、赤色と青色の方眼紙の配置のペアを1つ求めよ。

3 <= H,W <= 500

帰納的考察(Editorial見た)

1. ぶっちゃけさっぱり分からんかった

――壁――

2. こういう全探索もBFSも難しそうな問題は貪欲解が無いか探そう
3. 今回は解説見れば一発で分かる
4. こういう地頭を求められるやつなぁ

実装

http://agc004.contest.atcoder.jp/submissions/870304

int H, W;
string a[500];
//-----------------------------------------------------------------
int main() {
	cin >> H >> W;
	rep(y, 0, H) cin >> a[y];
 
	rep(y, 0, H) {
		cout << "#";
		rep(x, 1, W - 1) {
			if (y % 2 == 0)
				cout << "#";
			else
				cout << a[y][x];
		}
		cout << "." << endl;
	}
	cout << endl;
	rep(y, 0, H) {
		cout << ".";
		rep(x, 1, W - 1) {
			if (y % 2 == 1)
				cout << "#";
			else
				cout << a[y][x];
		}
		cout << "#" << endl;
	}
}