#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x ostream& operator<<(ostream& os, const pair& p){ return os << "{" << p.first << ", " << p.second << "}"; } template ostream& operator<<(ostream& os, const vector& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template ostream& operator<<(ostream& os, const set& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template ostream& operator<<(ostream& os, const map& obj) { os << "map{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template void take(vector& vec, int n) { vec.resize(n); for (int i = 0; i < n; ++i) cin >> vec[i]; } #ifdef ONLINE_JUDGE #define dump(expr) ; #else #define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; } #endif using EdgeCost = ll; struct E { int fr, to, eid; EdgeCost cost; E(int fr_, int to_, int eid_, EdgeCost cost_) : fr(fr_), to(to_), eid(eid_), cost(cost_) {} friend ostream &operator<<(ostream &os, const E &e) { os << "(" << e.fr << " -> " << e.to << ")"; return os; } }; using V = vector; struct G { int n, e_count; vector adj, rev; G(int n_) : n(n_), e_count(0), adj(n), rev(n) {} void add_directed_edge(int fr, int to, EdgeCost cost = (EdgeCost)1) { assert(0 <= fr && fr < n); assert(0 <= to && to < n); E e(fr, to, e_count++, cost); adj[fr].push_back(e); rev[to].push_back(e); } void add_undirected_edge(int fr, int to, EdgeCost cost = (EdgeCost)1) { assert(0 <= fr && fr < n); assert(0 <= to && to < n); E e1(fr, to, e_count, cost), e2(to, fr, e_count++, cost); adj[fr].push_back(e1); rev[to].push_back(e1); adj[to].push_back(e2); rev[to].push_back(e2); } }; // Hopcroft-Karp, O(sqrt(N) * M) // Only works for non-weighted edges struct BipartiteMatching { const int INFTY = numeric_limits::max() / 2; int nil; vector pair_val; vector dist_val; bool dfs(G &g, int j) { if (j == nil) return true; for (auto e : g.adj[j]) { if (dist_val[pair_val[e.to]] == dist_val[j] + 1 && dfs(g, pair_val[e.to])) { pair_val[e.to] = j; pair_val[j] = e.to; return true; } } dist_val[j] = INFTY; return false; } int exec(G &g, int n1, int n2) { // left vertices: [0, n1) // right vertices: [n1, n1 + n2) assert((int)g.adj.size() == n1 + n2); nil = n1 + n2; pair_val.assign(n1 + n2 + 1, nil); int res = 0; for (;;) { queue q; dist_val.assign(n1 + n2 + 1, INFTY); for (int j : range(n1 + n2)) { if (pair_val[j] == nil) { dist_val[j] = (EdgeCost)0; q.push(j); } } dist_val[nil] = INFTY; while (!q.empty()) { int j = q.front(); q.pop(); if (j == nil) continue; for (auto it : g.adj[j]) { if (dist_val[pair_val[it.to]] == INFTY) { dist_val[pair_val[it.to]] = dist_val[j] + 1; q.push(pair_val[it.to]); } } } if (dist_val[nil] == INFTY) break; for (int j : range(n1 + n2)) if (pair_val[j] == nil && dfs(g, j)) res++; } return res; } }; namespace solver { template struct In2 { T1 a; T2 b; friend std::istream& operator>>(std::istream& is, In2& obj) { T1 t1; T2 t2; is >> t1 >> t2; obj = {t1, t2}; return is; } }; template struct In3 { T1 a; T2 b; T3 c; friend std::istream& operator>>(std::istream& is, In3& obj) { T1 t1; T2 t2; T3 t3; is >> t1 >> t2 >> t3; obj = {t1, t2, t3}; return is; } }; int n, m; vector vs; void read() { cin >> n >> m; take(vs, n); } using RetType = int; RetType run() { map, int> mp1, mp2; int cntw = 0, cntb = 0; for (int i : range(n)) for (int j : range(m)) { if (vs[i][j] == 'w') mp1[{i, j}] = cntw++; if (vs[i][j] == 'b') mp2[{i, j}] = cntb++; } int n1 = (int)mp1.size(), n2 = (int)mp2.size(); G g(n1 + n2); for (int i : range(n)) for (int j : range(m)) { if (vs[i][j] != '.') { int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1}; for (int r : range(4)) { int i2 = i + dy[r]; int j2 = j + dx[r]; if (mp1.count({i, j}) && mp2.count({i2, j2})) { g.add_undirected_edge(mp1[{i, j}], n1 + mp2[{i2, j2}]); } } } } dump(g.adj); BipartiteMatching bm; int m1 = bm.exec(g, n1, n2); int res = m1 * 100; cntw -= m1; cntb -= m1; int m2 = min(cntw, cntb); res += m2 * 10; cntw -= m2; cntb -= m2; res += cntw + cntb; return res; } } // namespace template void run(F f) { if constexpr (std::is_same_v) f(); else cout << f() << endl; } int main(int argc, char** argv) { cerr << fixed << setprecision(12); cout << fixed << setprecision(12); int testcase = 1; if (argc > 1) testcase = atoi(argv[1]); while (testcase--) { solver::read(); } run(solver::run); }