方針

黒マスは増やすことしか出来ないため、すでに条件を満たしていない（つまり、隣接に \(3\) 個以上の黒マスがある）白マスはいずれ黒く塗る必要があります。 そのような白マスを好きな順番で、条件を満たさない白マスが無くなるまで塗っていけば良いです。

注意点

白マスを黒く塗った結果新たに条件を満たさない白マスが生まれることがある点に注意してください。 下手な実装をするとTLEになってしまうので、計算量を \(O(N^2)\) 程度に収める工夫が必要です。例えば、条件を満たさない白マスを毎回 \(O(N^2)\) の計算量で探していると、白マスを黒く塗る回数は最悪 \(O(N^2)\) 個あることもあるため \(O(N^4)\) の計算量になってしまいます。

解法

BFSのような実装を行います。

1. 全マスをチェックし、条件を満たさない白マスを黒く塗り、キューに挿れる
2. キューから \(1\) マス取り出し、そのマスに隣接する白マスを見て、条件を満たさなくなっていたら黒く塗ってキューに挿れる
3. キューが空でないなら 2. に戻って繰り返す

これで 1. が \(O(N^2)\)、2.～3. が \(1\) ステップあたり \(O(1)\) でステップ数は \(N^2\) 回以下なので、全体の計算量は \(O(N^2)\) です。

実装例

#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
const vector<P> dij = {{-1,0}, {0,-1}, {1,0}, {0,1}};

int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) cin >> s[i];
  queue<P> q;

  int ans = 0;
  auto check = [&](int i, int j) {
    if (s[i][j] == '#') return;
    int cnt = 0;
    for (auto [di,dj] : dij) {
      int ni = i+di, nj = j+dj;
      if (ni<0 || ni>=n || nj<0 || nj>=n) continue;
      if (s[ni][nj] == '#') cnt++;
    }
    if (cnt <= 2) return;
    s[i][j] = '#';
    ans++;
    q.emplace(i,j);
  };
  
  for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
    check(i,j);
  }

  while (!q.empty()) {
    auto [i,j] = q.front(); q.pop();
    for (auto [di,dj] : dij) {
      int ni = i+di, nj = j+dj;
      if (ni<0 || ni>=n || nj<0 || nj>=n) continue;
      check(ni,nj);
    }
  }

  cout << ans << endl;
  return 0;
}