// 入力をscanfにしたときの速度差テスト用 #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define minus(c) memset(c, -1, sizeof c) const int Max = 110890; int dx[] = {-1,0,1,0,-1,1,1,-1}; int dy[] = {0,-1,0,1,-1,-1,1,1}; char VisMark = ' '; char RingMark = 'o'; int N, M; char G[1010][1010]; int ring_lens[Max]; vector tree[Max]; // to, cost template constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y> q; q.emplace(sy, sx); G[sy][sx] = RingMark; while(!q.empty()) { int y, x; tie(y, x) = q.front(); q.pop(); rep(i, 8) { // 'x'は8方向 int ny = y + dy[i], nx = x + dx[i]; if(!in_range(ny, nx, N, M)) { continue; } if(G[ny][nx] != 'x') { continue; } G[ny][nx] = RingMark; ret ++; q.emplace(ny, nx); } } return ret; }; auto get_next_depth_ring = [&](int sy, int sx) { vector> ret; queue> q; q.emplace(sy, sx); G[sy][sx] = VisMark; // 次の深さの輪を見つけるために、同じ深さ輪の間の '.' を訪れるBFS while(!q.empty()) { int y, x; tie(y, x) = q.front(); q.pop(); rep(i, 4) { // 4方向で輪を跨がずに'.'を消す int ny = y + dy[i], nx = x + dx[i]; if(!in_range(ny, nx, N, M)) { continue; } // 同じ深さの輪の間の '.' if(G[ny][nx] == '.') { G[ny][nx] = VisMark; q.emplace(ny, nx); } // 'x' は輪の要素なので、一つ見つけてあとは塗りつぶす if(G[ny][nx] == 'x') { ret.emplace_back(ny, nx, get_ring_len(ny, nx)); } } } return std::move(ret); }; // 同じ深さの木の葉が左から並ぶ (y, x, ノード番号) // '.'が連続する領域をノードと捉える queue> leaves; leaves.emplace(0, 0, 0); int nextch = 1; // BFS木を作る while(!leaves.empty()) { int ly, lx, leaf; tie(ly, lx, leaf) = leaves.front(); leaves.pop(); auto ring_nodes = get_next_depth_ring(ly, lx); for(auto && e: ring_nodes) { int y, x, len; tie(y, x, len) = e; tree[leaf].emplace_back(nextch); ring_lens[nextch] = len; rep(k, 8) { // 8方向で輪を跨ぐ'.'を見つける int ny = y + dy[k], nx = x + dx[k]; if(!in_range(ny, nx, N, M)) { continue; } if(G[ny][nx] == '.') { leaves.emplace(ny, nx, nextch); break; } } nextch++; } } } int dp[Max][2]; int rec(int curr, bool par_used = true) { auto& ret = dp[curr][par_used]; if(ret + 1) { return ret; } if(tree[curr].empty()) { return ret = par_used ? 0 : ring_lens[curr]; } ret = 0; if(par_used) { rep(i, tree[curr].size()) { ret += rec(tree[curr][i], false); } } else { int r1 = ring_lens[curr]; for(auto && e: tree[curr]) { r1 += rec(e, true); } int r2 = 0; for(auto && e: tree[curr]) { r2 += rec(e, false); } ret = max(r1, r2); } return ret; } int main() { scanf("%d %d", &N, &M); N += 2, M += 2; rep(i, M) G[0][i] = '.'; REP(i, 1, N-1) { G[i][0] = '.'; scanf("%s", G[i]+1); G[i][M-1] = '.'; } rep(i, M) G[N-1][i] = '.'; make_tree(); minus(dp); cout << rec(0) << endl; return 0; }