#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const vector& vec){for(int i=0; i ostream& operator , (ostream& os, T& val){ return os << " " << val;} template ostream& operator >> (ostream& os, T& val){ return os << " " << val;} using namespace std; class UnionFindTree{ struct base_node{ int parent; int rank; int size; }; vector node; public: UnionFindTree(int n){ node.resize(n); for(int i=0; i node[y].rank){ node[y].parent = x; node[x].size += node[y].size; }else{ node[x].rank++; unite(x,y); } } }; int dx[] = {0,0,1,-1,1,-1,1,-1}; int dy[] = {1,-1,0,0,1,1,-1,-1}; int main(){ int n,m; cin >> n,m; vector v(n+2, string(m+2, '.')); for(int i=1; i<=n; i++){ string tmp; cin >> tmp; v[i] = '.' + tmp + '.'; } n+=2; m+=2; UnionFindTree uft(n*m); for(int i=0; i=n) continue; if(jj < 0 || jj>=m) continue; if(v[ii][jj] == 'x') uft.unite(i*m+j, ii*m+jj); } } int t=0; set s; for(int i=0;i> G; queue q; vector visit( n*m , false); set next; vector> w(n, vector(m, -1)); {//round q.push(0); visit[0] = true; while(q.size()){ auto pos = q.front(); q.pop(); int r = pos/m; int c = pos%m; w[r][c] = 0; for(int k=0; k<4; k++){ int rr = r+dy[k]; int cc = c+dx[k]; if(rr < 0 || rr>=n) continue; if(cc < 0 || cc>=m) continue; if(visit[rr*m + cc]) continue; if(v[rr][cc] == 'x'){ next.insert(uft.find(rr*m + cc)); continue; } visit[rr*m + cc] = true; q.push(rr*m + cc); } } for(int unko : next){ q.push(unko); G[0].insert(unko); } } while(q.size()){ auto p = q.front(); q.pop(); int r = p/m; int c = p%m; int val = uft.find(p); set tmp; { function dfs0 = [&](int r, int c){ visit[r*m+c] = true; w[r][c] = val; for(int k=0; k<8; k++){ int rr = r+dy[k]; int cc = c+dx[k]; if(rr < 0 || rr>=n) continue; if(cc < 0 || cc>=m) continue; if(w[rr][cc] != -1) continue; if(v[rr][cc] == '.'){ tmp.insert(uft.find(rr*m + cc)); continue; } dfs0(rr,cc); } }; dfs0(r,c); } set next; function dfs = [&](int r, int c){ if(visit[r*m+c]) return; if(v[r][c] == 'x'){ next.insert(uft.find(r*m + c)); return; } w[r][c] = val; visit[r*m+c] = true; for(int k=0; k<4; k++){ int rr = r+dy[k]; int cc = c+dx[k]; if(rr < 0 || rr>=n) continue; if(cc < 0 || cc>=m) continue; if(w[rr][cc] != -1) continue; dfs(rr,cc); } }; for(int hoge : tmp) dfs(hoge/m, hoge%m); for(int ch : next){ G[p].insert(uft.find(ch)); q.push(ch); } } vector> memo(2); long long ans = 0; function dfs = [&](int pos, int use){ if(memo[use].find(pos) != memo[use].end()) return memo[use][pos]; long long ret = 0; if(pos != 0 && use) ret += uft.size(pos); for(auto ch : G[pos]){ if(use) ret += dfs(ch, 0); else ret += max(dfs(ch, 0), dfs(ch, 1)); } if(pos != 0) memo[use][pos] = ret; return ret; }; ans = max(dfs(0,0), dfs(0,1)); cout << ans << endl; return 0; }