#include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<std::ostream &operator<<(std::ostream&os,const std::pair&x){return os<<"("<std::ostream &operator<<(std::ostream&os,const std::vector&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<std::ostream &operator<<(std::ostream&os,const std::set&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<std::ostream&operator<<(std::ostream &os,const std::array &arr) {os<<'['<void print(std::ostream&os,const Tup &x,std::index_sequence){(void)(int[]){(os<(x)<<", ",0)...};} templatestd::ostream &operator<<(std::ostream&os,const std::tuple &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence());return os<(x)<<")";} const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m"; #define func_LINE_FILE NORMAL_FAINT<<" in "<"<> adj; std::vector mt, idx, p; std::vector> es; void rematch(int u, int v, int w= -1) { if (w= mt[u], mt[u]= v; w == -1 || mt[w] != u) return; if (es[u][1] == -1) { rematch(mt[w]= es[u][0], w); } else rematch(es[u][0], es[u][1]), rematch(es[u][1], es[u][0]); } int f(int x) { return (idx[x] != ret || p[x] == -1) ? x : (p[x]= f(p[x])); } bool check(int root) { std::queue que; es[root]= {-1, -1}, idx[root]= ret, p[root]= -1, que.push(root); for (int x, u, v, w; !que.empty();) { x= que.front(), que.pop(); for (int y: adj[x]) { if (y == root) continue; if (mt[y] == -1) { return rematch(mt[y]= x, y), true; } else if (idx[y] == ret) { if (u= f(x), v= f(y), w= root; u == v) continue; for (; u != root || v != root; es[u]= {x, y}, u= f(es[mt[u]][0])) { if (v != root) std::swap(u, v); if (es[u][0] == x && es[u][1] == y) { w= u; break; } } for (int t= f(x); t != w; t= f(es[mt[t]][0])) idx[t]= ret, p[t]= w, que.push(t); for (int t= f(y); t != w; t= f(es[mt[t]][0])) idx[t]= ret, p[t]= w, que.push(t); } else if (idx[mt[y]] != ret) es[y]= {-1, -1}, es[mt[y]]= {x, -1}, idx[mt[y]]= ret, p[mt[y]]= y, que.push(mt[y]); } } return false; } public: Matching(int n): n(n), ret(0), adj(n), mt(n, -1), idx(n, -1), p(n), es(n) {} void add_edge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); } std::pair> get_matching() { for (int i= 0; i < n; i++) if (mt[i] == -1) ret+= check(i); return std::make_pair(ret, mt); } }; using namespace std; namespace yukicoder421 { signed main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector S(N); int bsize= 0, wsize= 0; for (int i= 0; i < N; i++) { cin >> S[i]; for (int j= 0; j < M; j++) bsize+= S[i][j] == 'b', wsize+= S[i][j] == 'w'; } Matching graph(N * M); int e= 0; for (int i= 0; i < N; i++) { for (int j= 0; j < M; j++) if ((i + j) & 1 && S[i][j] == 'b') { if (i > 0 && S[i - 1][j] == 'w') graph.add_edge(i * M + j, (i - 1) * M + j); if (i + 1 < N && S[i + 1][j] == 'w') graph.add_edge(i * M + j, (i + 1) * M + j); if (j > 0 && S[i][j - 1] == 'w') graph.add_edge(i * M + j, i * M + j - 1); if (j + 1 < M && S[i][j + 1] == 'w') graph.add_edge(i * M + j, i * M + j + 1); } } if (bsize > wsize) swap(bsize, wsize); int x= graph.get_matching().first; int ans= 100 * x + 10 * (bsize - x) + wsize - bsize; cout << ans << '\n'; return 0; } } signed main() { cin.tie(0); ios::sync_with_stdio(0); yukicoder421::main(); return 0; }