AtCoder AGC 004 C - AND Grid (黄色, 700 点)

こういうの大好き！

問題へのリンク

問題概要

の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ

• S の黒マスはすべて縦横に連結である
• T の黒マスはすべて縦横に連結である
• S の黒マスに対応する部分と、T の黒マスに対応する部分との共通部分が A に丁度一致する

制約

• 
• A の外周は白マスである

考えたこと

こういうのはとりあえず、いくつかのケースで遊んでみると良さそう

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

とかは

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

という感じでできる。入れ子になってるとむずそう。こういうの

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

こういうのを攻略していくことで、一般論が見えてくるのではないかと思う。それも、実装しやすくて明快な一般論が欲しい！！！

パッと思いつくのは example 1 っぽい感じで

• S は、各黒マスから左方向に、黒マスをずらっと伸ばしていく
• T は、各黒マスから上方向に、黒マスをずらっと伸ばしていく

という感じ。でもこれだと余裕で被ってしまう。そもそも

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

こういう風な「内部の黒マス」は、S も T もどっちも、上下左右のどちらかには黒を伸ばさないといけない。四マスのうちのどれを S に、どれを T に割り当てたらよいのだろうか？？？

パリティへ

こういうのを見ると、なんとなくパリティが絡みそうな気がしてくる。そもそも example がミスリードで、「一方は左に、もう一方は上に」という風にして被らせないのは至難の技なんだ。

それだったら、パリティで分岐して平行に伸ばした方がいい。つまり、こういう感じ。

ooooooooo  .........
.o.o#o.o.  o.o.#.o.o
.o.#.#.o.  o.o#o#o.o
.o#o#.#o.  o.#.#.#.o
.#.#.#.#.  o#o#o#o#o
.o#o#o#o.  o.#.#.#.o
.o.#.#.o.  o.o#o#o.o
.o.o#o.o.  o.o.#.o.o
.........  ooooooooo

• S の方は、偶数列を塗りたくる
• T の方は、奇数列を塗りたくる

という風にすれば、両者が被らなくて済むのだ。そして塗りたくったものが連結である必要があるので

• S の方は上も塗りたくる
• T の方は下も塗りたくる

という風にすればぴったり。これ、本当に上手い具合にちゃんと連結になってる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    vector<string> S = fi, T = fi;
    for (int w = 0; w < W; ++w) S[0][w] = '#', T[H-1][w] = '#';
    for (int w = 0; w < W; ++w) {
        for (int h = 1; h < H-1; ++h) {
            if (w % 2 == 1) S[h][w] = '#';
            else T[h][w] = '#';
        }
    }
    for (int h = 0; h < H; ++h) cout << S[h] << endl;
    cout << endl;
    for (int h = 0; h < H; ++h) cout << T[h] << endl;
    cout << endl;
}