#include using namespace std; #define rep(i, a) for (int i = 0; i < (a); i++) #define rep2(i, a, b) for (int i = (a); i < (b); i++) #define repr(i, a) for (int i = (a) - 1; i >= 0; i--) #define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--) template bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); } template bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } typedef long long ll; struct UnionFind { vector parent, size; UnionFind(int n) : parent(n), size(n, 1) { for (int i = 0; i < n; i++) parent[i] = i; } int operator[](int x) { return parent[x] == x ? x : (parent[x] = operator[](parent[x])); } bool merge(int x, int y) { if ((x = operator[](x)) == (y = operator[](y))) return false; parent[x] = parent[y] = size[x] > size[y] ? parent[x] : parent[y]; size[x] = size[y] = size[x] + size[y]; return true; } }; int dy[] = { 1, 1, 1, 0, 0, -1, -1, -1 }; int dx[] = { 1, 0, -1, 1, -1, 1, 0, -1 }; int dy2[] = { 1, 0, -1, 0 }; int dx2[] = { 0, -1, 0, 1 }; set G[1010101]; set rG[1010101]; ll dp[1010101][2]; void dfs(int curr, int prev, UnionFind &uf) { dp[curr][1] += uf.size[curr]; for (int next : G[curr]) if (next != prev && next != curr) { dfs(next, curr, uf); dp[curr][0] += max(dp[next][0], dp[next][1]); dp[curr][1] += dp[next][0]; } } int main() { int h, w; cin >> h >> w; vector g(h); rep(i, h) cin >> g[i]; UnionFind uf(h * w); rep(y, h) rep(x, w) if (g[y][x] == 'x') { rep(k, 8) { int ny = y + dy[k]; int nx = x + dx[k]; if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue; if (g[ny][nx] != 'x') continue; uf.merge(y * w + x, ny * w + nx); } } static bool used[1010101]; static bool vis[1010][1010]; rep(i, h) rep(j, w) if (g[i][j] == 'x') { int rt = uf[i * w + j]; if (used[rt]) continue; used[rt] = true; int y = i + 1; int x = j; if (g[y][x] == 'x') continue; queue> q; q.emplace(y, x); vis[y][x] = true; while (!q.empty()) { tie(y, x) = q.front(); q.pop(); rep(k, 4) { int ny = y + dy2[k]; int nx = x + dx2[k]; if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue; if (g[ny][nx] == 'x') { if (rt != uf[ny * w + nx]) { int nn = uf[ny * w + nx]; G[rt].insert(nn); rG[nn].insert(rt); } } else if (chmax(vis[ny][nx], true)) { q.emplace(ny, nx); } } } } memset(used, 0, sizeof(used)); memset(vis, 0, sizeof(vis)); rep(j, w) rep(i, h) if (g[i][j] == 'x') { int rt = uf[i * w + j]; if (used[rt]) continue; used[rt] = true; int y = i; int x = j + 1; if (g[y][x] == 'x') continue; queue> q; q.emplace(y, x); vis[y][x] = true; while (!q.empty()) { tie(y, x) = q.front(); q.pop(); rep(k, 4) { int ny = y + dy2[k]; int nx = x + dx2[k]; if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue; if (g[ny][nx] == 'x') { if (rt != uf[ny * w + nx]) { int nn = uf[ny * w + nx]; G[rt].insert(nn); rG[nn].insert(rt); } } else if (chmax(vis[ny][nx], true)) { q.emplace(ny, nx); } } } } ll ans = 0; rep(i, h) rep(j, w) { int c = i * w + j; if (uf[c] != c) continue; if (g[i][j] == 'x' && rG[c].size() == 0) { dfs(c, -1, uf); ans += max(dp[c][0], dp[c][1]); } } cout << ans << endl; return 0; }