#include #include #include #include #include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() #define mod 1000000007 #define inf 2000000007 #define mp make_pair #define pb push_back typedef long long ll; using namespace std; template inline void output(T a, int p) { if(p) cout << fixed << setprecision(p) << a << "\n"; else cout << a << "\n"; } // end of template // goal, capacity, index of reverse edge struct edge { int to, cap, rev; }; // O(EV^2) class Dinic{ public: int V; vector> G; vector L; vector I; Dinic(int v){ G.resize(v), L.resize(v), I.resize(v); V = v; } // add edge void add(int from, int to, int cap){ G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size() - 1}); } // label dist from s void bfs(int s){ L.assign(V, -1); queue q; L[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); rep(i, G[v].size()){ edge &e = G[v][i]; if (e.cap > 0 && L[e.to] < 0) { L[e.to] = L[v] + 1; q.push(e.to); } } } } // search positive path int dfs(int v, int t, int f){ if (v == t) return f; for (int &i = I[v]; i < G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && L[v] < L[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } // calc max flow int max_flow(int s, int t){ int flow = 0; for (;;) { bfs(s); if (L[t] < 0) return flow; I.assign(V, 0); int f; while ((f = dfs(s, t, inf)) > 0) { flow += f; } } } }; int main() { cin.tie(0); ios::sync_with_stdio(0); // source code int H, W; cin >> H >> W; vector A(H); rep(i, H) cin >> A[i]; Dinic mf(H * W + 2); int white = 0, bitter = 0; rep(i, H) rep(j, W){ if(A[i][j] == 'w') { white++; mf.add(0, i * W + j + 1, 1); } if(A[i][j] == 'b') { bitter++; mf.add(i * W + j + 1, H * W + 1, 1); } } int ret = 0; rep(i, H) rep(j, W) rep(k, H) rep(l, W){ if(A[i][j] == 'w' && A[k][l] == 'b'){ if(abs(i - k) + abs(j - l) == 1){ mf.add(i * W + j + 1, k * W + l + 1, 1); } } } ret += mf.max_flow(0, H * W + 1); white -= ret, bitter -= ret; output(ret * 100 + min(white, bitter) * 10 + abs(white - bitter), 0); return 0; }