#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; } void traceRing(int r, int c, int curId, int ringId[BUF][BUF]) { static int dr[] = {-1, -1, -1, 0, 1, 1, 1, 0}; static int dc[] = {-1, 0, 1, 1, 1, 0, -1, -1}; ringId[r][c] = curId; 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) { traceRing(nr, nc, curId, ringId); } } } void colorArea(int initR, int initC, int currId, bool visited[BUF][BUF], vector< set > &adjRing, int ringId[BUF][BUF]) { queue Q; Q.push(Point(initR, initC)); visited[initR][initC] = true; while (!Q.empty()) { Point curr = Q.front(); Q.pop(); static int dr[] = {-1, 0, 1, 0}; static int dc[] = {0, 1, 0, -1}; for (int i = 0; i < 4; ++i) { int nr = curr.r + dr[i]; int nc = curr.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]) { Q.push(Point(nr, nc)); visited[nr][nc] = true; } } } } int doDp(bool preUsed, int curr, vector< vector > &dp, vector< set > &adjRing, int ringId2cnt[BUF]) { 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, ringId2cnt); B += doDp(false, *it, dp, adjRing, ringId2cnt); } return ret = (preUsed ? B : max(A + ringId2cnt[curr], B)); } void work() { int nRing = 1; static int ringId[BUF][BUF]; memset(ringId, -1, sizeof(ringId)); for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) if (b[i][j] == 'x' && ringId[i][j] == -1) { traceRing(i, j, nRing++, ringId); } static int ringId2cnt[BUF]; memset(ringId2cnt, 0, sizeof(ringId2cnt)); for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) if (ringId[i][j] != -1) { ++ringId2cnt[ringId[i][j]]; } vector< set > adjRing(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, ringId2cnt) << endl; } int main() { read(); work(); return 0; }