ABC460 D問題 Repeatedly Repeating

Atcoder Beginner Contest 460 D - Repeatedly Repeating

問題リンク

問題文

行 列のマス目があります。このマス目の上から 行目、左から 列目のマスをマス と呼びます。

すべてのマスは白または黒で塗られています。マス目の情報は 個の長さ の文字列によって与えられ、の
文字目が . のときマス
は白で、
の文字目が # のときマスは黒で塗られています。

あなたは、以下の操作を 回行います。

• すべてのマスに対して同時に以下の規則で色の塗り替えを行う。
  • 操作前に白く塗られているマスは、そのマスに隣接する黒く塗られているマスが存在するとき、またそのときに限り黒く塗り替える。ただし、マス とマス
    が隣接しているとは、片方のマスがもう片方のマスの 近傍にある、すなわち であることを指す。
  • 操作前に黒く塗られているマスは、白く塗り替える。

操作を終えた後に各マスが何色で塗られているか求めてください。

出力

行出力せよ。
各行に ., # からなる長さの文字列をつずつ出力せよ。行目の文字列の文字目は回の操作を行った後にマスが白で塗られているとき.に、黒で塗られているとき#になるようにせよ。

アプローチ

真っ白な盤面に黒を１つ置き、条件の通り色を繰り返し塗り替えしてみると黒と白の波紋ができるのがわかる。
一度波が通ったところは白と黒で入れ替わり続けるはずなので、初めて波紋が通るタイミングだけを考えてみよう。
前述のケースで限界まで波紋が広がると、それ以降は白と黒が毎ターン入れ替わるだけなのがわかる。つまり、塗り替えた回数の偶奇で色が決まる。そして偶数回目で初めて黒になるマス（すなわち、一番近い黒への距離が偶数のマス）は、それ以降の偶数回目はいつも黒のはずだ。よって、各マスの一番近い黒への距離を多始点BFSで求める。初めて波紋が通るタイミングで以降も決まるから、黒の点が２つ以上あっても問題ない。

ただし、最初の時点で黒である場所が最後必ず黒とは限らないことに注意。 の黒い正方形を想像してみると、真ん中のマスは３回目以降の奇数回目で黒になることがわかる。
この正方形をもっと大きくしてみよう。ある程度大きめの黒の正方形があるとき、一度色を塗り替えると正方形を囲む輪が現れ、塗り替えし続けると波紋ができる。
黒については１ターン操作した後を基準に何ターンで黒になるかを考えればよいわけだ。１ターンずらしているので、最も近い白との距離 - 1 が偶数かを判別する。

あとは盤面が全て白色であったり黒色である場合のケアをすればよい。このとき波紋は生まれず、真っ白な盤面になる。

解答

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

// 8方向への移動用のやつ
const int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<string> S(H);
    bool has_black = false;
    bool has_white = false;

    for (int i = 0; i < H; ++i) {
        cin >> S[i];
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == '#') has_black = true;
            if (S[i][j] == '.') has_white = true;
        }
    }

    // 全面が真っ白か真っ黒なら真っ白にしておわり
    if (!has_black || !has_white) {
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                cout << '.';
            }
            cout << "\n";
        }
        return 0;
    }

    // ↓↓それ以外のとき↓↓
    vector<vector<int>> dist_from_black(H, vector<int>(W, INF));
    vector<vector<int>> dist_from_white(H, vector<int>(W, INF));
    
    queue<pair<int, int>> q_black, q_white;

    // 初期状態をすべてキューへ
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == '#') {
                dist_from_black[i][j] = 0;
                q_black.push({i, j});
            } else {
                dist_from_white[i][j] = 0;
                q_white.push({i, j});
            }
        }
    }

    //黒からの距離を数えてく
    while (!q_black.empty()) {
        auto [r, c] = q_black.front();
        q_black.pop();

        for (int dir = 0; dir < 8; ++dir) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            // 盤面内に収まっていて、未訪問のとき更新
            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                if (dist_from_black[nr][nc] == INF) {
                    dist_from_black[nr][nc] = dist_from_black[r][c] + 1;
                    q_black.push({nr, nc});
                }
            }
        }
    }

    //白からの距離を数えてく
    while (!q_white.empty()) {
        auto [r, c] = q_white.front();
        q_white.pop();

        for (int dir = 0; dir < 8; ++dir) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                if (dist_from_white[nr][nc] == INF) {
                    dist_from_white[nr][nc] = dist_from_white[r][c] + 1;
                    q_white.push({nr, nc});
                }
            }
        }
    }

    // 最終的な盤面の構築
    for (int i = 0; i < H; ++i) {
        string ans_row = "";
        for (int j = 0; j < W; ++j) {
            int d = 0;
            // 距離の取得、黒マスならマイナス1
            if (S[i][j] == '.') {
                d = dist_from_black[i][j];
            } else {
                d = dist_from_white[i][j] - 1;
            }

            // 偶奇の判定
            if (d % 2 == 0) {
                ans_row += '#';
            } else {
                ans_row += '.';
            }
        }
        cout << ans_row << "\n";
    }

    return 0;
}