#include #include #include #include #include using namespace std; #define rep(i, S, E) for(int i=(S); i<(E); i++) struct Edge{ int to; int cap; int rev; }; struct Dinic{ vector> G; vector levels; vector iters; const long long INF = 1<<30; int n; Dinic(){ ; } Dinic(int _n){ G.reserve(_n); levels.resize(_n, 0); iters.resize(_n, 0); n = _n; } void set_graph(int from, int to, int cap){ Edge e = {to, cap, (int)G[to].size()}; G[from].emplace_back(e); e = {from, 0, (int)G[from].size()-1}; G[to].emplace_back(e); return; } void bfs(int s){ fill(levels.begin(), levels.end(), -1); queue Q; Q.push(s); levels[s] = 0; while (!Q.empty()){ int v = Q.front(); Q.pop(); for (Edge& e : G[v]){ if (e.cap > 0 && levels[e.to] < 0){ levels[e.to] = levels[v] + 1; Q.push(e.to); } } } return; } int dfs(int v, int t, int f){ if (v == t){ return f; } for (int& i=iters[v]; i 0 && levels[e.to] > levels[v]){ int _f = dfs(e.to, t, min(f, e.cap)); if (_f > 0){ e.cap -= _f; G[e.to][e.rev].cap += _f; return _f; } } } return 0; } int execute(int s, int t){ int flow = 0; while(true){ bfs(s); if(levels[t] < 0){ return flow; } fill(iters.begin(), iters.end(), 0); while(true){ int f = dfs(s, t, INF); if (f > 0){ flow += f; }else{ break; } } } return 0; } }; int N, M; char B[50][50]; bool isin(int x, int y){ if (0 <= x && x < N){ if (0 <= y && y < M){ return true; } } return false; } int main() { cin >> N >> M; rep(i, 0, N){ rep(j, 0, M){ cin >> B[i][j]; } } Dinic dinic(N*M+2); int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int w_cnt = 0, b_cnt = 0; rep(i, 0, N){ rep(j, 0, M){ if (B[i][j] != '.'){ if ((i%2==0 && j%2==0) || (i%2==1 && j%2==1)){ w_cnt++; dinic.set_graph(N*M, M*i+j, 1); rep(k, 0, 4){ if (isin(i+dy[k], j+dx[k])){ if (B[i+dy[k]][j+dx[k]] != '.'){ int from = M * i + j; int to = M * (i+dy[k]) + (j+dx[k]); dinic.set_graph(from, to, 1); } } } }else{ b_cnt++; dinic.set_graph(M*i+j, N*M+1, 1); } } } } int f = dinic.execute(N*M, N*M+1); int answer = 100 * f; w_cnt -= f; b_cnt -= f; while (w_cnt && b_cnt){ answer += 10; w_cnt--; b_cnt--; } if (w_cnt + b_cnt > 0) answer += (w_cnt + b_cnt); cout << answer << endl; return 0; }