問題
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; } }