Submission #69672968

---

Source Code Expand

// Problem: 'D - Ulam-Warburton Automaton'
// Contest: 'AtCoder - UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 425)'
// URL: 'https://atcoder.jp/contests/abc425/tasks/abc425_d'
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by competitive-companion.el (https://github.com/luishgh/competitive-companion.el)

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

vector<vector<int>> d;
vector<vector<bool>> vis, bl;

vector<vector<int>> g;
int h, w;

queue<pair<int, int>> q;
queue<pair<int, int>> q2;

const vector<pair<int, int>> moves = {
  {-1, 0},
  {+1, 0},
  {0,-1},
  {0, +1}
};

void bfs() {
  while (q.size() or q2.size()) {
    while (q.size()) {
      auto [x, y] = q.front();
      q.pop();
      if (vis[x][y]) continue;
      vis[x][y] = true;
      for (auto [dx, dy] : moves) {
        int wx = x + dx, wy = y + dy;
        if (wx < 0 or wx >= h or wy < 0 or wy >= w) continue;
        if (d[wx][wy] < d[x][y] + 1) continue;
        if (d[x][y] + 1 == d[wx][wy]) {
          // cerr << x+1 << ' ' << y+1 << " BLOCKS " << wx+ 1<< ' ' << wy+1 << endl;
          bl[wx][wy] = true;
        }
        else {
          bl[wx][wy] = false;
          d[wx][wy] = d[x][y] + 1;
          q2.emplace(wx, wy);
        }
      }
    }
    while (q2.size()) {
      auto [x, y] = q2.front();
      q2.pop();
      if (!bl[x][y]) q.emplace(x, y);
      // else cerr << x << ' ' << y << endl;
    }
  }
}

int main() {_;
  cin >> h >> w;
  g = vector(h, vector<int>(w));
  d = vector(h, vector<int>(w));
  vis = vector(h, vector<bool>(w));
  bl = vector(h, vector<bool>(w));
  for (int i = 0; i < h; i++) {
    string line; cin >> line;
    for (int j = 0; j < w; j++) {
      if (line[j] == '#') {
        g[i][j] = 1;
        q.emplace(i, j);
        d[i][j] = 0;
      }
      else g[i][j] = 0, d[i][j] = INF;
    }
  }

  bfs();
  ll ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      // if (!vis[i*h + j]) cerr << '.';
      // else cerr << '#';
      if (vis[i][j]) ans++;
    }
    // cerr << endl;
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result