Submission #74286638

---

Source Code Expand

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

int main(){
  ll H,W,ans = 0,x,s,t;
  cin >> H >> W;
  vector<vector<char>> S(H,vector<char>(W));
  queue<pair<ll,ll>> BFS;
  for(ll i = 0;i < H;i++){
    for(ll j = 0;j < W;j++){
      cin >> S[i][j];
    }
  }
  for(ll i = 0;i < H;i++){
    for(ll j = 0;j < W;j++){
      if(S[i][j] == '#'){
        continue;
      }
      x = 1;
      BFS.push({i,j});
      S[i][j] = '#';
      while(BFS.size() > 0){
        s = BFS.front().first;
        t = BFS.front().second;
        if(s == 0 || s == H - 1 || t == 0 || t == W - 1){
          x = 0;
        }
        if(s - 1 >= 0 && S[s - 1][t] == '.'){
          BFS.push({s - 1,t});
          S[s - 1][t] = '#';
        }
        if(s + 1 < H && S[s + 1][t] == '.'){
          BFS.push({s + 1,t});
          S[s + 1][t] = '#';
        }
        if(t - 1 >= 0 && S[s][t - 1] == '.'){
          BFS.push({s,t - 1});
          S[s][t - 1] = '#';
        }
        if(t + 1 < W && S[s][t + 1] == '.'){
          BFS.push({s,t + 1});
          S[s][t + 1] = '#';
        }
        BFS.pop();
      }
      ans+=x;
    }
  }
  cout << ans;
}

Submission Info

Judge Result