Submission #69667526

---

Source Code Expand

  //#include "atcoder/modint"
  #pragma GCC optimize("Ofast")
  #include "atcoder/all"
  #include <bits/stdc++.h>
  #include  <string>
  using namespace std;
  using namespace atcoder;
  #define int long long
    template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
  template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
  //const int MOD =1e9+7;
  //constexpr int MOD =10;
  constexpr int MOD =998244353;
  const long long M1=167772161,M2=469762049,M3=1224736769;
  //const int MOD =31607;
  using mint = static_modint<MOD>;
  //using mint = double;
  //using mint = modint;
  ostream& operator << (ostream& ost, const mint& m){ost << m.val();return ost;}
  istream& operator >> (istream& ost,  mint& m){int a;ost >> a;m=a;return ost;}
  double time_limit = 100.0,start_temp=0.01,end_temp=0.0;
  std::mt19937 rng(std::random_device{}()); 

  signed main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int h,w;
    cin>>h>>w;
    string s[h];
    int c[h][w],ans=0;
    vector<pair<int,int>> v;
        for(int i=0;i<h;i++)cin>>s[i];
    for(int i=0;i<h;i++){
      
      
      for(int j=0;j<w;j++){
        c[i][j]=0;
        if(s[i][j]=='#')ans++;
        if(i!=0&&s[i-1][j]=='#')c[i][j]++;
        if(i!=h-1&&s[i+1][j]=='#')c[i][j]++;
        if(j!=0&&s[i][j-1]=='#')c[i][j]++;
        if(j!=w-1&&s[i][j+1]=='#')c[i][j]++;
        if(s[i][j]!='#'&&c[i][j]==1)v.push_back({i,j});
      }
    }
    while(!v.empty()){
      vector<pair<int,int>> nv,vx;
      for(auto p:v){

        int i=p.first,j=p.second;
        //cerr<<p.first<<" "<<p.second<<endl;
        if(c[i][j]!=1)continue;
        vx.push_back({i,j});
      }
      for(auto p:vx){
        
        int i=p.first,j=p.second;
        s[i][j]='#';
        ans++;
        if(i!=0){
          c[i-1][j]++;
          if(s[i-1][j]!='#'&&c[i-1][j]==1)nv.push_back({i-1,j});
        }
        if(i!=h-1){
          c[i+1][j]++;
          if(s[i+1][j]!='#'&&c[i+1][j]==1)nv.push_back({i+1,j});
        }
        if(j!=0){
          c[i][j-1]++;
          if(s[i][j-1]!='#'&&c[i][j-1]==1)nv.push_back({i,j-1});
        }
        if(j!=w-1){
          c[i][j+1]++;
          if(s[i][j+1]!='#'&&c[i][j+1]==1)nv.push_back({i,j+1});
        }
       
      }
      v=nv;
      
    }
    cout<<ans<<endl;
    




  
 
   

  }

Submission Info

Judge Result