#include using namespace std; #define rep(i,n) for(int i = 0; i < (int)(n); ++i) struct Dinic { public: using Flow = int; Dinic(int n_) : g(n_), n(n_) {} Flow maximumFlow(int s_, int t_) { s = s_; t = t_; Flow res = 0; while (levelize()) { prog.assign(n, 0); res += augment(s, numeric_limits::max()); } return res; } void addEdge(int u, int v, Flow c) { g[u].push_back({ u,v,c,0,(int)g[v].size() }); g[v].push_back({ v,u,c,c,(int)g[u].size() - 1 }); } private: struct Edge { int s, d; Flow c, f; int r; }; vector> g; int n, s, t; vector level, prog; bool levelize() { queue q; q.push(s); level.assign(n, -1); level[s] = 0; while (q.size()) { int v = q.front(); q.pop(); if (v == t) break; for (auto &e : g[v]) { if (level[e.d] == -1 && residue(e) != 0) { level[e.d] = level[v] + 1; q.push(e.d); } } } return level[t] != -1; } Flow augment(int v, Flow lim) { Flow res = 0; if (v == t) return lim; for (int &i = prog[v]; i < (int)g[v].size(); ++i) { if (lim == 0) break; auto &e = g[v][i]; if (level[v] < level[e.d] && residue(e) != 0) { Flow aug = augment(e.d, min(lim, residue(e))); e.f += aug; reverse(e).f -= aug; res += aug; lim -= aug; } } return res; } Flow residue(const Edge& e) { return e.c - e.f; } Edge &reverse(const Edge &e) { return g[e.d][e.r]; } }; // renzoku*100 -> sirokuro*20 -> nokori*1 int h,w; char g[55][55]; int enc(int i, int j){ return i*w + j; } int main(){ while(cin >> h >> w){ Dinic mf(50*50 + 2); // b->w int B = 2500, W = B+1; int cb = 0, cw = 0; rep(i,h) cin >> g[i]; rep(i,h)rep(j,w){ if(g[i][j] == 'b'){ mf.addEdge(B, enc(i,j), 1); ++cb; } if(g[i][j] == 'w'){ mf.addEdge(enc(i,j), W, 1); ++cw; } if(g[i][j] != 'b') continue; int di[] = {0,1,0,-1}; int dj[] = {1,0,-1,0}; rep(d,4){ int ni = i + di[d]; int nj = j + dj[d]; if(ni < 0) continue; if(nj < 0) continue; if(ni >= h) continue; if(nj >= w) continue; if(g[ni][nj] != 'w') continue; // cout << i << ' ' << j << ' ' << ni << ' ' << nj << endl; // cout << g[i][j] << ' ' << g[ni][nj] << endl; mf.addEdge(i*w+j, ni*w+nj, 1); } } int a = mf.maximumFlow(B,W); int b = (min(cb, cw) - a); assert(b >= 0); int c = (cb + cw) - 2*a - 2*b; // cout << a << ' ' << b << ' ' << c << endl; cout << a*100 + b*10 + c << endl; } }