#include using namespace std; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FORR(x,arr) for(auto&& x:arr) #define FOR(i,a,b) for (int i = (a); i < (b); i++) #define RFOR(i,a,b) for (int i = (b)-1; i >= (a); i--) #define REP(i,n) for (int i = 0; i < (n); i++) #define RREP(i,n) for (int i = (n)-1; i >= 0; i--) #define ALL(x) (x).begin(), (x).end() #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++) #define BIT(n) (1LL<<(n)) #define SZ(x) ((int)(x).size()) typedef long long ll; // ------------------------------------- int N, M; string G[1010]; bool used[1010][1010]; int sy, sx; int lef, top, rig, bot; typedef struct Ring { int top, lef, bot, rig, sz; } Ring; int DY[8] = {1, 0, -1, 0, 1, 1, -1, -1}; int DX[8] = {0, 1, 0, -1, 1, -1, 1, -1}; int dfs(int y, int x) { bot = max(bot, y); rig = max(rig, x); top = min(top, y); lef = min(lef, x); used[y][x] = true; REP(d, 8) { int ny = y + DY[d]; int nx = x + DX[d]; if (ny < 0 || ny >= N) continue; if (nx < 0 || nx >= M) continue; if (G[ny][nx] == 'x' && !used[ny][nx]) { return dfs(ny, nx) + 1; } } return 1; } vector rings; typedef pair IB; map memo; map > con2; int dfs2(int i, bool use) { IB key = {i, use}; if (memo.find(key) != memo.end()) return memo[key]; Ring& r = rings[i]; int ret1 = r.sz; int ret2 = 0; FORR(j, con2[i]) { ret2 += dfs2(j, false); } if (!use) { FORR(j, con2[i]) { ret1 += dfs2(j, true); } return memo[key] = max(ret1, ret2); } return memo[key] = ret2; } int main() { cin >> N >> M; REP(i, N) cin >> G[i]; REP(y, N) { REP(x, M) { if (G[y][x] == 'x' && !used[y][x]) { top = bot = y; lef = rig = x; int sz = dfs(y, x); //_P("(%d,%d),(%d,%d), %d\n", top, lef, bot, rig, sz); rings.push_back({top, lef, bot, rig, sz}); } } } int nr = SZ(rings); set soto; REP(i, nr) { soto.insert(i); } sort(ALL(rings), [](const Ring& a, const Ring& b) { return a.top != b.top ? a.top < b.top : a.lef != b.lef ? a.lef < b.lef : a.bot != b.bot ? a.bot < b.bot : a.rig < b.rig;} ); map con; REP(i, nr) FOR(j, i+1, nr) { Ring& ri = rings[i]; Ring& rj = rings[j]; if (ri.sz < 14) continue; if (ri.top < rj.top && ri.lef < rj.lef && ri.rig > rj.rig && ri.bot > rj.bot) { // rj in ri soto.erase(j); if (con.find(j) == con.end()) { con[j] = i; } else { int pi = con[j]; if (rings[pi].sz > rings[i].sz) { con[j] = i; } } } } REP(i, nr) { if (con.find(i) != con.end()) { con2[con[i]].push_back(i); } } int ans = 0; FORR(i, soto) { //_P("soto: %d\n", i); ans += dfs2(i, false); } cout << ans << endl; return 0; }