题解：AT_abc425_d [ABC425D] Ulam-Warburton Automaton

N1tr0us_Acid · 2025-09-29 23:37:08 · 题解

很好的推理，令我的大脑旋转。

\texttt{Solution}

我们可以这么想，假定我们现在到了第 i 时刻，且在 1 到 i - 1 时刻的所有其他可被染色的格子都已经染色，那么自然可以发现，第 i 时刻染色的格子必然与第 i - 1 时刻染色的格子相邻，否则这个格子在第 i 时刻前就可以被染色，与我们的假定矛盾了。

那么就很好做了，我们一直记录上一次染色了那些格子，然后对这些格子的相邻格子进行判断并染色即可，这个操作可以使用滚动维护，省空间。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
vector <char> vec[N];
int h, w;
int ans;
typedef pair <int, int> pii;
vector <pii> npos[2];
int pre, now;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool check(int x, int y) {
    if(x < 1 || y < 1 || x > h || y > w) return 0;
    int cnt = 0;
    for (int i = 0; i < 4; i ++) {
        int tox = x + dx[i], toy = y + dy[i];
        if(tox < 1 || toy < 1 || tox > h || toy > w) continue ;
        cnt += vec[tox][toy] == '#';
    }
    return cnt == 1;
}
signed main(void) {
    cin >> h >> w;
    pre = 0, now = 1;
    for (int i = 1; i <= h; i ++) {
        vec[i].emplace_back('*');
        for (int j = 1; j <= w; j ++) {
            char k;
            cin >> k;
            vec[i].emplace_back(k);
            if(k == '#') npos[pre].emplace_back(make_pair(i, j)), ans ++;
        }
        vec[i].emplace_back('*');
    }
    while (npos[pre].size()) {
        npos[now].clear();
        for (auto [u, v] : npos[pre]) {
            for (int i = 0; i < 4; i ++) {
                int tox = u + dx[i], toy = v + dy[i];
                if(check(tox, toy) && vec[tox][toy] != '#') {
                    ans ++;
                    npos[now].emplace_back(make_pair(tox, toy));
                }
            }
        }
        for (auto [u, v] : npos[now]) vec[u][v] = '#';
        swap(pre, now);
    }
    cout << ans << endl;
    return 0;
}