#include #include #include #include #include #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; // const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}, // dx[] = {0, -1, -1, -1, 0, 1, 1, 1}; struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(10); } } iosetup; /*-------------------------------------------------*/ struct HopcroftKarp { vector match; HopcroftKarp(int left, int right) : left(left), graph(left), match(left + right, -1), level(left), used(left, -1) {} void add_edge(int u, int v) { graph[u].emplace_back(left + v); } int solve() { int res = 0; while (true) { bfs(); int tmp = 0; REP(i, left) if (match[i] == -1) { if (dfs(i)) ++tmp; ++timestamp; } if (tmp == 0) return res; res += tmp; } } private: int left, timestamp = 0; vector > graph; vector level, used; void bfs() { fill(ALL(level), -1); queue que; REP(i, left) { if (match[i] == -1) { que.emplace(i); level[i] = 0; } } while (!que.empty()) { int ver = que.front(); que.pop(); for (int e : graph[ver]) if (match[e] != -1 && level[match[e]] == -1) { level[match[e]] = level[ver] + 1; que.emplace(match[e]); } } } bool dfs(int ver) { used[ver] = timestamp; for (int e : graph[ver]) { int tmp = match[e]; if (tmp == -1 || (used[tmp] < timestamp && level[tmp] == level[ver] + 1 && dfs(tmp))) { used[ver] = timestamp; match[e] = ver; match[ver] = e; return true; } } return false; } }; int main() { int n, m; cin >> n >> m; vector s(n); REP(i, n) cin >> s[i]; map, int> white, bitter; REP(i, n) REP(j, m) { if (s[i][j] == 'w') { int sz = white.size(); white[{i, j}] = sz; } else if (s[i][j] == 'b') { int sz = bitter.size(); bitter[{i, j}] = sz; } } int w = white.size(), b = bitter.size(); HopcroftKarp hk(w, b); REP(i, n) REP(j, m) { if (s[i][j] == 'w') { REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (0 <= y && y < n && 0 <= x && x < m && s[y][x] == 'b') { hk.add_edge(white[{i, j}], bitter[{y, x}]); } } } } int type3 = hk.solve(); w -= type3; b -= type3; int type2 = min(w, b); w -= type2; b -= type2; cout << w + b + 10 * type2 + 100 * type3 << '\n'; return 0; }