/* -*- coding: utf-8 -*- * * 421.cc: No.421 しろくろチョコレート - 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_H = 50; const int MAX_W = 50; const int MAX_N = MAX_H * MAX_W; /* typedef */ typedef vector vi; typedef vector vb; /* global variables */ string flds[MAX_H]; int ids[MAX_H][MAX_W]; vi nbrs[MAX_N]; /* subroutines */ bool max_match_rec(const vi *nbrs, int u, vi &matches, vb &visited) { if (u < 0) return true; const vi &nbru = nbrs[u]; for (vi::const_iterator vit = nbru.begin(); vit != nbru.end(); vit++) { const int &v = *vit; if (! visited[v]) { visited[v] = true; if (max_match_rec(nbrs, matches[v], matches, visited)) { matches[u] = v; matches[v] = u; return true; } } } return false; } int max_match(const int n, int l, const vi *nbrs) { vi matches(n, -1); int count = 0; for (int u = 0; u < l; u++) { vb visited(n, false); if (max_match_rec(nbrs, u, matches, visited)) count++; } return count; } /* main */ int main() { int h, w; cin >> h >> w; memset(ids, -1, sizeof(ids)); int bn = 0, wn = 0; for (int y = 0; y < h; y++) { cin >> flds[y]; for (int x = 0; x < w; x++) switch (flds[y][x]) { case 'b': ids[y][x] = bn++; break; case 'w': ids[y][x] = wn++; break; } } for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) if (ids[y][x] >= 0) { bool bf = (flds[y][x] == 'b'); int u = bf ? ids[y][x] : ids[y][x] + bn; if (x < w - 1 && ids[y][x + 1] >= 0) { int v = bf ? ids[y][x + 1] + bn : ids[y][x + 1]; nbrs[u].push_back(v); nbrs[v].push_back(u); } if (y < h - 1 && ids[y + 1][x] >= 0) { int v = bf ? ids[y + 1][x] + bn : ids[y + 1][x]; nbrs[u].push_back(v); nbrs[v].push_back(u); } } int mm = max_match(bn + wn, bn, nbrs); //printf("bn=%d, wn=%d, mm=%d\n", bn, wn, mm); bn -= mm, wn -= mm; int sc = mm * 100 + min(bn, wn) * 10 + abs(bn - wn); printf("%d\n", sc); return 0; }