#include #define rep(i,a,b) for(int i=a;i struct MaxFlow { struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} }; int MV; vector> E; vector itr, lev; MaxFlow() {} MaxFlow(int n) { init(n); } void init(int n) { MV = n; itr = vector(MV), lev = vector(MV); E = vector>(MV); } void add_edge(int x, int y, V cap, bool undir = false) { E[x].push_back(edge(y, (int)E[y].size(), cap)); E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0)); } void bfs(int cur) { rep(i, 0, MV) lev[i] = -1; queue q; lev[cur] = 0; q.push(cur); while (q.size()) { int v = q.front(); q.pop(); for(auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to); } } V dfs(int from, int to, V cf) { if (from == to) return cf; for (; itr[from]cap>0 && lev[from]to]) { V f = dfs(e->to, to, min(cf, e->cap)); if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(int from, int to) { V fl = 0, tf; while (1) { bfs(from); if (lev[to]<0) return fl; rep(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits::max()))>0) fl += tf; } } }; struct BipartiteMatching { int N, M; MaxFlow mf; BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); } void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); } int match() { rep(a, 0, N) mf.add_edge(N + M, a, 1); rep(b, 0, M) mf.add_edge(N + b, N + M + 1, 1); return mf.maxflow(N + M, N + M + 1); } // マッチング相手を返す(無いなら-1) int whois(int a) { for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N; return -1; } }; //--------------------------------------------------------------------------------------------------- int H, W; string S[50]; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { -1, 0, 1, 0 }; //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W; rep(i, 0, H) cin >> S[i]; vector b, w; rep(y, 0, H) rep(x, 0, W) { if (S[y][x] == 'b') b.push_back(y * W + x); if (S[y][x] == 'w') w.push_back(y * W + x); } sort(b.begin(), b.end()); sort(w.begin(), w.end()); BipartiteMatching bm(b.size(), w.size()); rep(y, 0, H) rep(x, 0, W) if(S[y][x] == 'b'){ rep(i, 0, 4) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 || W <= xx) continue; if (yy < 0 || H <= yy) continue; if (S[yy][xx] != 'w') continue; int bb = lower_bound(b.begin(), b.end(), y * W + x) - b.begin(); int ww = lower_bound(w.begin(), w.end(), yy * W + xx) - w.begin(); bm.add_edge(bb, ww); } } int p100 = bm.match(); int rb = b.size() - p100; int rw = w.size() - p100; int p10 = min(rb, rw); int ans = 100 * p100 + 10 * p10 + (b.size() - p100 - p10) + (w.size() - p100 - p10); cout << ans << endl; } /* ` `` ` . ` .g,` Welcome To My Coding Space! .MMe `(F(#~ `.J, `.M/7b. dD.N; (#=#: `` db (m.#` Wl(@ jF ` `` ` ` ` ..+kMMN;_(Y> `(TD d$..gHN_ ` `` ...... ` ` ` `..gMB61+1+dK `- `. .TM@^(d% `` `` ..JggHHMMHHYYTHMMMNmgJ.. .kB6z?1+z1+
+H8+=??=?=?=???=?=?=z1&z1?==?1dMdNcHmJ1+1JMMR1?z??Ne1dM9+?(MF(MI+jMf .`.``.`.. (TNaHr`.`.TNmN:(MR+?zMK(M$` `.`.``dF ` J#<=1;?Wp .``.` J#>dN, ..``.`dF` `_UmMn .`..`..`..`. JMYT1<;;;>>>>>;>>?Wo ..`. dK1=dN,`..``.MN+ .dMMe .`.``.`.`.` d#<;>>>>;>>>>;>>>>(N,`.. -MK1llvWm. JM?Mp. ` ` ` .M9+?Me`.`..`.`.`` JN(>;>>;>>;>>>;>>>>>>>;>>>>>;>>>>>>>>>>>>>>><(W$(M8TIllllllllllllllllzvMo ` ` ` (#1?==1?===z?TNa,.` `` (Ne<<>>>>><;><;jgMMY1HK1lllllllllllllllllllJMp ` .Ne&g&x1=?=?==?1zTHNmJ-...dNgJ++++&ggMH9=~ .M9Izlllllllllllllllllll1WF ` ` _???MK<=??=??1z?(MM@!d#M#Y""""=