#include #include #include #include #include #define r first #define c second using namespace std; typedef pair Point; const int BUF = 1005; int row, col; char b[BUF][BUF]; void read() { cin >> row >> col; for (int i = 0; i < row + 2; ++i) { for (int j = 0; j < col + 2; ++j) { b[i][j] = '.'; } } for (int i = 1; i <= row; ++i) { for (int j = 1; j <= col; ++j) { cin >> b[i][j]; } } row += 2; col += 2; } bool isInside(int r, int c) { return 0 <= r && r < row && 0 <= c && c < col; } int traceRing(int r, int c, int curId, int ringId[BUF][BUF]) { int ringSize = 0; ringId[r][c] = curId; static int dr[] = {-1, -1, -1, 0, 1, 1, 1, 0}; static int dc[] = {-1, 0, 1, 1, 1, 0, -1, -1}; for (int i = 0; i < 8; ++i) { int nr = r + dr[i]; int nc = c + dc[i]; if (isInside(nr, nc) && b[nr][nc] == 'x' && ringId[nr][nc] == -1) { ringSize += traceRing(nr, nc, curId, ringId); } } return ringSize + 1; } void colorArea(int r, int c, int currId, bool visited[BUF][BUF], vector< set > &adjRing, int ringId[BUF][BUF]) { visited[r][c] = true; static int dr[] = {-1, 0, 1, 0}; static int dc[] = {0, 1, 0, -1}; for (int i = 0; i < 4; ++i) { int nr = r + dr[i]; int nc = c + dc[i]; if (!isInside(nr, nc)) continue; if (b[nr][nc] == 'x') { if (currId != ringId[nr][nc]) adjRing[currId].insert(ringId[nr][nc]); } else if (!visited[nr][nc]) { colorArea(nr, nc, currId, visited, adjRing, ringId); } } } int doDp(bool preUsed, int curr, vector< vector > &dp, vector< set > &adjRing, vector &ringId2size) { int &ret = dp[preUsed][curr]; if (ret != -1) return ret; int A = 0; // use current int B = 0; // do not use current for (set::iterator it = adjRing[curr].begin(); it != adjRing[curr].end(); ++it) { A += doDp(true, *it, dp, adjRing, ringId2size); B += doDp(false, *it, dp, adjRing, ringId2size); } return ret = (preUsed ? B : max(A + ringId2size[curr], B)); } void work() { int nRing = 1; static int ringId[BUF][BUF]; memset(ringId, -1, sizeof(ringId)); vector ringId2size; ringId2size.push_back(0); for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) if (b[i][j] == 'x' && ringId[i][j] == -1) { int ringSize = traceRing(i, j, nRing++, ringId); ringId2size.push_back(ringSize); } vector< set > adjRing; adjRing.assign(nRing, set()); static bool visited[BUF][BUF]; memset(visited, 0, sizeof(visited)); colorArea(0, 0, 0, visited, adjRing, ringId); for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) if (!visited[i][j] && ringId[i][j] != -1) { colorArea(i, j, ringId[i][j], visited, adjRing, ringId); } vector< vector > dp(2, vector(nRing, -1)); cout << doDp(false, 0, dp, adjRing, ringId2size) << endl; } int main() { read(); work(); return 0; }