Submission #74275075

---

Source Code Expand

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

namespace nachia {

struct DsuFast{
private:
    std::vector<int> w;
public:
    DsuFast(int n = 0) : w(n, -1) {}
    int leader(int u){
        if(w[u] < 0) return u;
        return w[u] = leader(w[u]);
    }
    int operator[](int u){ return leader(u); }
    int merge(int u, int v){
        u = leader(u);
        v = leader(v);
        if(u == v) return u;
        if(-w[u] < -w[v]) std::swap(u, v);
        w[u] += w[v];
        w[v] = u;
        return u;
    }
    int size(int u){ return -w[leader(u)]; }
    bool same(int u, int v){ return leader(u) == leader(v); }
};

} // namespace nachia
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

void testcase(){
  ll H, W; cin >> H >> W;
  V<string> A(H); REP(y,H) cin >> A[y];
  nachia::DsuFast dsu(H*W);
  auto Idx = [&](ll y, ll x) { return y* W + x; };
  REP(y,H) REP(x,W-1) if(A[y][x] == '.' && A[y][x+1] == '.') dsu.merge(Idx(y,x), Idx(y,x+1));
  REP(y,H-1) REP(x,W) if(A[y][x] == '.' && A[y+1][x] == '.') dsu.merge(Idx(y,x), Idx(y+1,x));
  V<ll> wt(H*W, 1);
  REP(y,H) REP(x,W) if(y == 0 || y == H-1 || x == 0 || x == W-1) wt[dsu[Idx(y,x)]] = 0;
  ll ans = 0;
  REP(y,H) REP(x,W) if(A[y][x] == '.' && dsu[Idx(y,x)] == Idx(y,x)) ans += wt[Idx(y,x)];
  cout << ans << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}

Submission Info

Judge Result