#include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) template bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; } using namespace std; struct point_t { int y, x; }; const int dy[] = { -1, 1, 0, 0, -1, 1, -1, 1 }; const int dx[] = { 0, 0, -1, 1, -1, -1, 1, 1 }; int main() { int h, w; cin >> h >> w; vector > is_x(h, vector(w)); repeat (y,h) repeat (x,w) { char c; cin >> c; is_x[y][x] = c == 'x'; } auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; }; vector > rings; vector > rev(h, vector(w, -1)); function make_ring = [&](int y, int x) { if (not is_on_field(y, x)) return; if (not is_x[y][x]) return; if (rev[y][x] != -1) return; rings.back().push_back((point_t) { y, x }); rev[y][x] = rings.size() - 1; repeat (i,8) make_ring(y + dy[i], x + dx[i]); }; repeat (y,h) repeat (x,w) if (is_x[y][x] and rev[y][x] == -1) { rings.emplace_back(); make_ring(y, x); } int n = rings.size(); rings.emplace_back(); vector > is_in(n + 1); vector > used(h, vector(w)); function analyze_inclusion = [&](int y, int x, int r) { if (not is_on_field(y, x)) return; if (used[y][x]) return; if (rev[y][x] != -1 and rev[y][x] != r) { is_in[r].insert(rev[y][x]); return; } used[y][x] = true; repeat (i,4) analyze_inclusion(y + dy[i], x + dx[i], r); }; repeat (y,h) { analyze_inclusion(y, 0, n); analyze_inclusion(y, w-1, n); } repeat (x,w) { analyze_inclusion( 0, x, n); analyze_inclusion(h-1, x, n); } repeat (y,h) repeat (x,w) if (rev[y][x] != -1 and not used[y][x]) { int r = rev[y][x]; for (point_t p : rings[r]) { analyze_inclusion(p.y, p.x, r); } } vector > memo(2, vector(n + 1)); function calculate_score = [&](int r) { for (int s : is_in[r]) calculate_score(s); memo[1][r] += rings[r].size(); // use r for (int s : is_in[r]) memo[1][r] += memo[0][s]; for (int s : is_in[r]) memo[0][r] += memo[1][s]; // don't use r setmax(memo[1][r], memo[0][r]); }; calculate_score(n); cout << memo[1][n]<< endl; return 0; }