Submission #74288714

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;

int H,W;
bool dfs(int v,vector<vector<int>> G,vector<bool>&seen,bool &ok){
  if(seen[v])return ok;
  seen[v]=true;
  if(v%W==0 || (v-v%W)/W==0 || v%W==W-1 || (v-v%W)/W==H-1)ok=false;
  for(auto nv:G[v]){
    if(!dfs(nv,G,seen,ok))ok=false;
  }
  return ok;
  
  
}



int main(){
  cin>>H>>W;
  vector<string> S(H);
  vector<vector<int>>  G(H*W);
  
  rep(i,H){
    cin>>S[i];
    rep(j,W){
      
      if(S.at(i).at(j)=='.'){
        if(i>0 && S.at(i-1).at(j)=='.'){
          G[W*i+j].push_back(W*(i-1)+j);
          G[W*(i-1)+j].push_back(W*i+j);
        }
        if(j>0 && S[i].at(j-1)=='.'){
          G[W*i+j].push_back(W*i+j-1);
          G[W*i+j-1].push_back(W*i+j);
        }
      }
    }
  }
  
  //v%W==0 || (v-v%W)/W==0 || v%W==W-1 || (v-v%W)/W==W-1
  /*
  int v=68;
  cout <<v%W<<endl;
  cout <<(v-v%W)/W<<endl;
  cout <<v%W<<endl;
  cout <<(v-v%W)/W<<endl;
  */
  
  vector<bool>seen(H*W,false);
  int answer=0;
  rep(i,H){
    rep(j,W){
      if(S.at(i).at(j)=='.'&&  !seen[i*W+j]){
      
        bool ok=true;
        if(dfs(i*W+j,G,seen,ok)){
          answer++;
          //cout <<W*i+j<<' ';
          //cout <<i<<' '<<j<<endl;
        }
      }
    }
  }
  cout <<answer<<endl;
  //*/
  
  
  
}

Submission Info

Judge Result