#line 1 "main.cpp" #include #line 6 "/mnt/c/Users/araar/documents/kyopro/library/graph/FordFulkerson.cpp" template class FordFulkerson { public: struct edge { int to; T cap; int rev; }; int n; std::vector> g; std::vector used; FordFulkerson(int n = 0) : n(n), g(n), used(n) { } void add_edge(int from, int to, T cap) { assert(0 <= from && from < n); assert(0 <= to && to < n); assert(0 <= cap); g[from].push_back((edge){to, cap, int(g[to].size())}); g[to].push_back((edge){from, 0LL, int(g[from].size() - 1)}); } T dfs(int v, int goal_v, T flow) { if(v == goal_v) return flow; used[v] = true; for(int i = 0; i < (int)g[v].size(); i++) { edge &e = g[v][i]; if(!used[e.to] && e.cap > 0) { T next_flow = dfs(e.to, goal_v, std::min(flow, e.cap)); if(next_flow > 0) { e.cap -= next_flow; g[e.to][e.rev].cap += next_flow; return next_flow; } } } return 0; } T max_flow(int s, int t, T ma = std::numeric_limits::max()) { assert(0 <= s && s < n); assert(0 <= t && t < n); T flow = 0; while(1) { used = std::vector(n, false); T f = dfs(s, t, ma); if(f == 0) return flow; flow += f; } } }; #line 3 "main.cpp" using namespace std; #define rep(i, n) for(int i = 0; i < int(n); i++) using ll = long long; using P = pair; int main() { int h, w; cin >> h >> w; vector s(h); rep(i, h) cin >> s[i]; FordFulkerson mcf_graph(h * w + 2); int st = h * w, go = h * w + 1; rep(i, h) { rep(j, w) { // cout << i * w + j << " "; if(s[i][j] == '.') continue; else if(s[i][j] == 'w') { mcf_graph.add_edge(st, i * w + j, 1); if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * w + j, i * w + j + 1, 1); if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge(i * w + j, (i + 1) * w + j, 1); } else { mcf_graph.add_edge(i * w + j, go, 1); if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * w + j + 1, i * w + j, 1); if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge((i + 1) * w + j, i * w + j, 1); } } // cout << endl; } int flowcnt = mcf_graph.max_flow(st, go); int bcnt = 0, wcnt = 0; rep(i, h) rep(j, w) { if (s[i][j] == 'w') wcnt++; else if (s[i][j] == 'b') bcnt++; } cout << 100 * flowcnt + (min(bcnt, wcnt) - flowcnt) * 10 + max(bcnt, wcnt) - min(bcnt, wcnt) << endl; // cout << flowcnt << endl; return 0; }