#include #include #include #include #include #include using namespace std; struct Dinic { static const int INF = 1e9; struct E { //to,容量,逆辺のindex int to, cap, rev; E(int t, int c, int r) { to = t; cap = c; rev = r; } }; //最大頂点数 int MAX_V; vector>G; Dinic(int max_v) { MAX_V = max_v; G.resize(MAX_V); } //有向辺 inline void add_edge(int from, int to, int cap) { if (from == to)return; G[from].push_back(E(to, cap, G[to].size())); G[to].push_back(E(from, 0, G[from].size()-1)); } //無向辺 inline void add_undirected_edge(int from, int to, int cap) { if (from == to)return; G[from].push_back(E(to, cap, G[to].size())); G[to].push_back(E(from, cap, G[from].size()-1)); } //深さ vectorlevel; //深さのラベル付け void bfs(int s) { level.assign(MAX_V, -1); queue que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < G[v].size(); i++) { E &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } //s -- v -- u -- t //tから深さ優先探索 int dfs(int s, int u, int crr) { if (s == u || crr == 0)return crr; int sum = 0; for (int i = 0; i < G[u].size(); i++) { E& e = G[u][i]; //t側 E& ee = G[e.to][e.rev]; //s側 int v = e.to; if (level[v] >= level[u] || ee.cap <= 0)continue; int f = dfs(s, v, min(crr - sum, ee.cap)); if (f <= 0)continue; //容量の更新 ee.cap -= f; e.cap += f; //流量の更新 sum += f; if (sum == crr)break; } return sum; } int max_flow(int s, int t) { int flow = 0; //tに流せなくなるまで while(1){ bfs(s); if (level[t] < 0)return flow; flow += dfs(s, t, INF); } } }; int main() { int N, M; cin >> N >> M; vector>cho(N); int w=0, b=0; for (int i = 0; i < N; i++) { cho[i].resize(M); for (int j = 0; j < M; j++) { char c; cin >> c; cho[i][j] = c; if (c == 'w')w++; else if (c == 'b')b++; } } setbs,ws; Dinic dn(2502); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (cho[i][j] == 'w') { ws.insert(i*M + j + 1); if (i > 0 && cho[i - 1][j] == 'b') { dn.add_edge(i*M + j + 1, (i - 1)*M + j + 1, 1); bs.insert((i - 1)*M + j + 1); } if (i < N - 1 && cho[i + 1][j] == 'b') { dn.add_edge(i*M + j + 1, (i + 1)*M + j + 1, 1); bs.insert((i + 1)*M + j + 1); } if (j > 0 && cho[i][j - 1] == 'b') { dn.add_edge(i*M + j + 1, i*M + j - 1 + 1, 1); bs.insert(i*M + j - 1 + 1); } if (j < M - 1 && cho[i][j + 1] == 'b') { dn.add_edge(i*M + j + 1, i*M + j + 1 + 1, 1); bs.insert(i*M + j + 1 + 1); } } } } for (auto itr = ws.begin(); itr != ws.end(); itr++) { dn.add_edge(0, *itr, 1); } for (auto itr = bs.begin(); itr != bs.end(); itr++) { dn.add_edge(*itr, N * M + 1, 1); } int ans = dn.max_flow(0, N*M+1); w -= ans; b -= ans; int pair = min(w,b); w -= pair; b -= pair; cout << ans * 100 + pair * 10 + w + b << endl; return 0; }