#include #include #include #include #include #include #include #include constexpr size_t di[] = {size_t(-1), 0, 1, 0}; constexpr size_t dj[] = {0, size_t(-1), 0, 1}; template struct Edge { size_t src, dst; Weight cost; Edge(size_t src, size_t dst, Weight cost=1): src(src), dst(dst), cost(cost) {} bool operator <(const Edge &rhs) const { if (cost != rhs.cost) return cost < rhs.cost; if (src != rhs.src) return src < rhs.src; return dst < rhs.dst; } }; template struct Graph: public std::vector>> { Graph(size_t n): std::vector>>(n) {} void connect_with(size_t src, size_t dst, Weight cost=1) { (*this)[src].emplace_back(src, dst, cost); (*this)[dst].emplace_back(dst, src, cost); } void connect_to(size_t src, size_t dst, Weight cost=1) { (*this)[src].emplace_back(src, dst, cost); } }; template size_t bipartite_match(const Graph &g, size_t mid) { std::vector pair(g.size(), -1); std::function &)> augment; augment = [&](size_t u, std::vector &visited) { if (u+1 == 0) return true; for (const Edge &e: g[u]) { if (visited[e.dst]) continue; visited[e.dst] = true; if (augment(pair[e.dst], visited)) { pair[e.src] = e.dst; pair[e.dst] = e.src; return true; } } return false; }; size_t match = 0; for (size_t i = 0; i < mid; ++i) { std::vector visited(g.size()); if (augment(i, visited)) ++match; } return match; } int main() { size_t N, M; scanf("%zu %zu", &N, &M); std::vector s(N); int w = 0; int b = 0; for (auto& si: s) { char buf[64]; scanf("%s", buf); si = buf; w += std::count(si.begin(), si.end(), 'w'); b += std::count(si.begin(), si.end(), 'b'); } std::vector> ind(N, std::vector(M)); size_t mid; { size_t cur = 0; for (size_t i = 0; i < N; ++i) for (size_t j = i%2; j < M; j += 2) ind[i][j] = cur++; mid = cur; for (size_t i = 0; i < N; ++i) for (size_t j = 1-i%2; j < M; j += 2) ind[i][j] = cur++; } Graph g(N*M); for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < M; ++j) { if (s[i][j] != 'w') continue; for (int k = 0; k < 4; ++k) { size_t ni = i + di[k]; size_t nj = j + dj[k]; if (!(ni < N && nj < M)) continue; if (s[ni][nj] != 'b') continue; g.connect_with(ind[i][j], ind[ni][nj]); } } } int max = bipartite_match(g, mid); int res = 100*max; w -= max; b -= max; if (w > b) std::swap(w, b); res += 10*w; res += b-w; printf("%d\n", res); }