Submission #69714466

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int h, w;
  cin >> h >> w;

  vector<string> s(h);
  for (int i=0; i<h; i++) {
    cin >> s.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  //////////////////// 処理 ////////////////////

  // 今回調査するやつ、次回調査するやつ、塗るの待機してるやつ
  // 重複を省きたいのでvectorじゃなくsetにする
  set<pair<int,int>> s0, s1, s2;

  // とりあえず、最初に黒マスの隣になっているやつを場外含め全部s0に入れる
  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
      if (s.at(i).at(j)=='#') {
        s0.emplace(i+1,j);
        s0.emplace(i-1,j);
        s0.emplace(i,j+1);
        s0.emplace(i,j-1);
        result++;
      }
    }
  }

  // 「調査予定が最初から空」になるまで調査する
  while (!s0.empty()) {

    // s0の中身全てに対して調査
    for (auto [i,j] : s0) {
      
      // 場外やもともと黒マスならスキップ
      if (i<0||i>=h||j<0||j>=w) continue;
      if (s.at(i).at(j)=='#') continue;

      // 周囲の黒マス数をチェック
      int count = 0;
      if (i>0&&s.at(i-1).at(j)=='#') count++;
      if (i<h-1&&s.at(i+1).at(j)=='#') count++;
      if (j>0&&s.at(i).at(j-1)=='#') count++;
      if (j<w-1&&s.at(i).at(j+1)=='#') count++;

      // 2マス以上あるならスキップ
      // 0であることはないので、ここを通過するのは1のときだけ
      if (count>1) continue;

      // 塗るの待機列に加える
      s2.emplace(i,j);

      // 周囲を次回調査予定に加える
      s1.emplace(i+1,j);
      s1.emplace(i-1,j);
      s1.emplace(i,j+1);
      s1.emplace(i,j-1);

    }

    // 待機列のやつを全部塗る
    for (auto [i,j] : s2) {
      s.at(i).at(j) = '#';
      result++;
    }
    s2.clear();

    // 次回調査予定を今回用に移動、次回用は空にする
    swap(s0,s1);
    s1.clear();
    
  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result