Submission #69669891

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int H, W; cin >> H >> W;
  vector<string> S(H); for(int i=0; i<H; i++) cin >> S[i];

  const int N = H*W;
  auto id = [&](int i, int j){ return i * W + j; };
  auto inside = [&](int i, int j){ return 0<= i&& i<H && 0<=j && j<W; };
  const int di[4] = {-1, 1, 0, 0};
  const int dj[4] = { 0, 0,-1, 1};

  vector<char> black(N, 0);
  vector<int> deg(N, 0);
  ll ans = 0;

  /// 初期黒を集める
  vector<int> initBlack;
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      if (S[i][j] == '#') {
        int v = id(i, j);
        black[v] = 1;
        ans++;
        initBlack.push_back(v);
      }
    }
  }
  // 初期黒から隣接白の黒隣接数を数える
  for (int v : initBlack) {
    int i = v/W, j = v%W;
    for (int d=0; d<4; d++) {
      int ni = i+di[d], nj = j+dj[d];
      if (!inside(ni, nj)) continue;
      int u = id(ni, nj);
      if (!black[u]) deg[u]++;
    }
  }

  // 黒化する集合
  vector<int> cur;
  for (int v=0; v<N; v++) {
    if (!black[v] && deg[v] == 1) {
      black[v] = 1;
      ans++;
      cur.push_back(v);
    }
  }

  vector<int> touched;
  vector<char> mark(N, 0);

  // 黒になる候補がなくなったら終了
  while (!cur.empty()) {
    // 今、黒になった頂点から、白隣接の deg をまとめて更新
    touched.clear();
    for (int v : cur) {
      int i = v/W, j = v%W;
      for (int d=0; d<4; d++) {
        int ni = i+di[d], nj = j+dj[d];
        if (!inside(ni, nj)) continue;
        int u = id(ni, nj);
        if (!black[u]) {
          deg[u]++;
          if (!mark[u]) { 
            mark[u] = 1; 
            touched.push_back(u); 
          }
        }
      }
    }
    // 次で黒化する集合をまとめて決定
    vector<int> next; next.reserve(touched.size());
    for (int u : touched) {
      if (!black[u] && deg[u] == 1) {
        black[u] = 1;
        ans++;
        next.push_back(u);
      }
      mark[u] = 0; // フラグを戻す
    }
    cur.swap(next);
  }

  cout << ans << '\n';
  return 0;
}

Submission Info

Judge Result