#define _USE_MATH_DEFINES #include using namespace std; #define int long long const int O = 1; struct Point { int x, y; Point() {} Point(int _x, int _y) { x = _x; y = _y; } }; int cntID = 0; struct Node { int id; int p; vector child; Node(int _p) { p = _p; id = cntID++; } }; int N, M; char fld[1003][1003]; const int dx8[8] = {1, 1, 0, -1, -1, -1, -1, 0}, dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const int dx4[4] = {1, 0, -1, 0}, dy4[4] = {0, 1, 0, -1}; bool IsOutside(int x, int y) { return x < -1 || M < x || y < -1 || N < y; } int PaintRing(int x, int y) { int res = 0; queue q; q.push(Point(x, y)); while (!q.empty()) { Point f = q.front(); q.pop(); if (fld[f.y + O][f.x + O] == '#') continue; fld[f.y + O][f.x + O] = '#'; res++; for (int i = 0; i < 8; i++) { int nx = f.x + dx8[i], ny = f.y + dy8[i]; if (IsOutside(nx, ny) || fld[ny + O][nx + O] != 'x') continue; q.push(Point(nx, ny)); } } return res; } void CreateTree(Node &node, int x, int y) { vector > child; queue q; q.push(Point(x, y)); while (!q.empty()) { Point f = q.front(); q.pop(); if (fld[f.y + O][f.x + O] == 'x') { int p = PaintRing(f.x, f.y); child.push_back(make_pair(Point(f.x, f.y), p)); continue; } if (fld[f.y + O][f.x + O] == '#') continue; fld[f.y + O][f.x + O] = '#'; for (int i = 0; i < 4; i++) { int nx = f.x + dx4[i], ny = f.y + dy4[i]; if (IsOutside(nx, ny) || fld[ny + O][nx + O] == '#') continue; q.push(Point(nx, ny)); } } /*for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%c", fld[i + O][j + O]); } puts(""); } puts("");*/ int res = 0; for (int i = 0; i < child.size(); i++) { for (int j = 0; j < 8; j++) { int nx = child[i].first.x + dx8[j], ny = child[i].first.y + dy8[j]; if (IsOutside(nx, ny) || fld[ny + O][nx + O] != '.') continue; child[i].first = Point(nx, ny); break; } node.child.push_back(Node(child[i].second)); CreateTree(node.child.back(), child[i].first.x, child[i].first.y); } } int memo[10000][2]; int Solve(Node &node, bool b) { if (memo[node.id][b] != -1) return memo[node.id][b]; int res = 0; for (int i = 0; i < node.child.size(); i++) { int ma = Solve(node.child[i], false); if (!b) ma = max(ma, Solve(node.child[i], true) + node.child[i].p); res += ma; } return memo[node.id][b] = res; } signed main() { fill((int*)memo, (int*)memo + 10000*2, -1); fill((char*)fld, (char*)fld + 1002*1002, '.'); cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> fld[i + O][j + O]; } } Node root(0); CreateTree(root, -1, -1); printf("%lld\n", Solve(root, false)); return 0; }