/* -*- coding: utf-8 -*- * * 348.cc: No.348 カゴメカゴメ - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 1000; const int MAX_M = 1000; const int MAX_T = MAX_N * MAX_M / 3 + 1; const int dxs[] = {1, 1, 0, -1, -1, -1, 0, 1}; const int dys[] = {0, -1, -1, -1, 0, 1, 1, 1}; const int INF = 1 << 30; /* typedef */ typedef vector vi; typedef queue qi; typedef pair pii; /* global variables */ int n, m, nm; string lines[MAX_N]; int used[MAX_N][MAX_M]; int prts[MAX_T], wis[MAX_T]; vi chlds[MAX_T]; int dp[MAX_T][2]; /* subroutines */ void print_flds() { for (int y = 0; y < n; y++) { for (int x = 0; x < m; x++) printf("%2d ", used[y][x]); putchar('\n'); } } int adj_ids(int x, int y, int ddi = 1) { int maxid = -1; for (int di = 0; di < 8; di += ddi) { int vx = x + dxs[di], vy = y + dys[di]; int id = (vx >= 0 && vx < m && vy >= 0 && vy < n) ? used[vy][vx] : 0; if (maxid < id) maxid = id; } return maxid; } inline int adj4_ids(int x, int y) { return adj_ids(x, y, 2); } int paint(int x0, int y0, int id, char ch, int ddi = 1) { if (lines[y0][x0] != ch || used[y0][x0] >= 0) return 0; int pn = 1; used[y0][x0] = id; queue q; q.push(pii(x0, y0)); while (! q.empty()) { pii u = q.front(); q.pop(); int &ux = u.first, &uy = u.second; for (int di = 0; di < 8; di += ddi) { int vx = ux + dxs[di], vy = uy + dys[di]; if (vx >= 0 && vx < m && vy >= 0 && vy < n && lines[vy][vx] == ch && used[vy][vx] < 0) { pn++; used[vy][vx] = id; q.push(pii(vx, vy)); } } } return pn; } inline int paint4(int x0, int y0, int id, char ch) { return paint(x0, y0, id, ch, 2); } void rec(int u) { dp[u][0] = 0; dp[u][1] = wis[u]; vi &chldu = chlds[u]; for (vi::iterator vit = chldu.begin(); vit != chldu.end(); vit++) { int &v = *vit; rec(v); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } } /* main */ int main() { cin >> n >> m; for (int y = 0; y < n; y++) cin >> lines[y]; nm = n * m; memset(used, -1, sizeof(used)); prts[0] = -1; int pn = 0; for (int y = 0; y < n; y++) pn += paint4(0, y, 0, '.'), pn += paint4(m - 1, y, 0, '.'); for (int x = 0; x < m; x++) pn += paint4(x, 0, 0, '.'), pn += paint4(x, n - 1, 0, '.'); //printf("pn=%d\n", pn); print_flds(); int tn = 1; while (pn < nm) { for (int y = 0; y < n; y++) for (int x = 0; x < m; x++) if (used[y][x] < 0) { if (lines[y][x] == 'x') { int aid = adj_ids(x, y); if (aid >= 0) { wis[tn] = paint(x, y, tn, 'x'); prts[tn] = aid; chlds[aid].push_back(tn); pn += wis[tn]; tn++; } } else { int aid = adj4_ids(x, y); if (aid >= 0) pn += paint4(x, y, aid, '.'); } } //printf("pn=%d\n", pn); print_flds(); } //for (int i = 0; i < tn; i++) printf("%d ", prts[i]); putchar('\n'); //for (int i = 0; i < tn; i++) printf("%d ", wis[i]); putchar('\n'); //for (int i = 0; i < tn; i++) printf("%lu ", chlds[i].size()); putchar('\n'); rec(0); printf("%d\n", dp[0][0]); return 0; }