#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int INF = INT_MAX; struct Edge { int to; int cap; int rev; Edge(int to = -1, int cap = -1, int rev = -1) { this->to = to; this->cap = cap; this->rev = rev; } }; const int MAX_N = 100; const int MAX_V = MAX_N * MAX_N + 10; int level[MAX_V]; int iter[MAX_V]; vector G[MAX_V]; void add_edge(int from, int to, int cap) { G[from].push_back(Edge(to, cap, G[to].size())); G[to].push_back(Edge(from, 0, G[from].size() - 1)); } void bfs(int s) { memset(level, -1, sizeof(level)); queue que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < (int) G[v].size(); ++i) { Edge *e = &G[v][i]; if (e->cap > 0 && level[e->to] < 0) { level[e->to] = level[v] + 1; que.push(e->to); } } } } int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < (int) G[v].size(); ++i) { Edge *e = &G[v][i]; if (e->cap > 0 && level[v] < level[e->to]) { int d = dfs(e->to, t, min(f, e->cap)); if (d > 0) { e->cap -= d; G[e->to][e->rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; for (;;) { bfs(s); if (level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } } } int DY[4] = {-1, 0, 1, 0}; int DX[4] = {0, 1, 0, -1}; int main() { int N, M; cin >> N >> M; string grid[N]; int counter[2] = {0, 0}; for (int i = 0; i < N; ++i) { cin >> grid[i]; for (int j = 0; j < M; ++j) { if (grid[i][j] == 'b') { counter[0]++; } else if (grid[i][j] == 'w') { counter[1]++; } } } int s = MAX_V - 2; int t = MAX_V - 1; for (int y = 0; y < N; ++y) { for (int x = 0; x < M; ++x) { int u = y * M + x; char ch = grid[y][x]; if (ch == '.') continue; if (ch == 'b') { add_edge(s, u, 1); } else { add_edge(u, t, 1); } if (ch == 'b') { for (int i = 0; i < 4; ++i) { int ny = y + DY[i]; int nx = x + DX[i]; if (ny < 0 || nx < 0 || N <= ny || M <= nx) continue; if (grid[ny][nx] == '.') continue; if (ch == grid[ny][nx]) continue; int v = ny * M + nx; add_edge(u, v, 1); } } } } int mc = max_flow(s, t); fprintf(stderr, "mc: %d\n", mc); int ans = 100 * mc; counter[0] -= mc; counter[1] -= mc; int pc = min(counter[0], counter[1]); ans += 10 * pc; counter[0] -= pc; counter[1] -= pc; ans += counter[0] + counter[1]; cout << ans << endl; return 0; }