#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX 1012 int n; int m; char room[MAX][MAX]; int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }; int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 }; struct st{ vector < pair > v; }; vector v; bool use[MAX][MAX]; int deg[MAX*MAX]; int id[MAX][MAX]; bool valid(int x, int y){ if (x < 0 || y < 0 || x >= n || y >= m){ return false; } if (use[x][y]){ return false; } if (room[x][y] == '.'){ return false; } return true; } inline void dfs(int a, int b,int ii){ use[a][b] = true; id[a][b] = ii; v[ii].v.push_back(make_pair(a, b)); for (int i = 0; i < 8; i++){ if (valid(a + dx[i], b + dy[i])){ dfs(a + dx[i], b + dy[i],ii); } } } bool done[MAX*MAX]; vector g[MAX*MAX]; bool s[MAX][MAX]; int dxx[] = { 0, 0, 1, -1 }; int dyy[] = { 1, -1, 0, 0 }; bool vv(int a, int b){ if (a < 0 || b < 0 || a >= n || b >= m){ return false; } if (room[a][b] == '.'){ return true; } return false; } bool v2(int a, int b){ if (a < 0 || b < 0 || a >= n || b >= m){ return false; } return true; } vector bfs(int a, int b){ vector r; s[a][b] = true; queue > q; q.push(make_pair(a, b)); while (!q.empty()){ a = q.front().first; b = q.front().second; q.pop(); for (int i = 0; i < 4; i++){ int aa = a + dxx[i]; int bb = b + dyy[i]; if (vv(aa, bb)){ if (s[aa][bb] == false){ s[aa][bb] = true; q.push(make_pair(aa, bb)); } } else{ if (v2(aa, bb)){ r.push_back(id[aa][bb]); } } } for (int i = 0; i < 8; i++){ if (dx[i] == 0 || dy[i] == 0){ continue; } if (vv(a + dx[i], b + dy[i])){ if (v2(a, b + dy[i]) && vv(a, b + dy[i]) == false){ if (v2(a + dx[i], b) && vv(a + dx[i], b) == false){ r.push_back(id[a + dx[i]][b]); continue; } } if (s[a + dx[i]][b + dy[i]] == false){ q.push(make_pair(a + dx[i], b + dy[i])); s[a + dx[i]][b + dy[i]] = true; } } else{ if (v2(a + dx[i], b + dy[i])){ r.push_back(id[a + dx[i]][b + dy[i]]); } } } } sort(r.begin(), r.end()); r.erase(unique(r.begin(), r.end()), r.end()); return r; } inline void f(int b){ done[b] = true; set vv; for (int i = 0; i < v[b].v.size(); i++){ for (int j = 0; j < 8; j++){ int xx = v[b].v[i].first + dx[j]; int yy = v[b].v[i].second + dy[j]; if (xx >= 0 && yy >= 0 && xx < n&&yy < m){ if (room[xx][yy] == '.'){ if (s[xx][yy] == false){ vector rr = bfs(xx, yy); for (int ii = 0; ii < rr.size(); ii++){ vv.insert(rr[ii]); } } } } } } if (vv.count(b)){ vv.erase(b); } for (auto it = vv.begin();it!= vv.end(); it++){ g[b].push_back((*it)); } vv.clear(); for (int i = 0; i < g[b].size(); i++){ f(g[b][i]); deg[g[b][i]]++; } } int dp[MAX*MAX][2]; inline void d(int b){ dp[b][0] = v[b].v.size(); for (int i = 0; i < g[b].size(); i++){ int id = g[b][i]; d(id); dp[b][1] += max(dp[id][0], dp[id][1]); dp[b][0] += dp[id][1]; } } int main(){ cin >> n >> m; for (int i = 0; i < n; i++){ scanf("%s", room[i]); } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (valid(i, j)){ v.push_back(st()); dfs(i, j, v.size() - 1); } } } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (i == 0 || j == 0 || i == n - 1 || j == m - 1){ if (room[i][j] == '.'){ if (s[i][j] == false){ bfs(i, j); } } } } } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (room[i][j] == 'x'){ if (done[id[i][j]] == false){ f(id[i][j]); } } } } int ans = 0; for (int i = 0; i < v.size(); i++){ if (deg[i] == 0){ d(i); ans += max(dp[i][0], dp[i][1]); } } cout << ans << endl; return 0; }