#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template static void amin(T &x, U y) { if(y < x) x = y; } template static void amax(T &x, U y) { if(x < y) x = y; } #define aut(r,v) auto r = (v) #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) int bipartiteMatching(const vector > &g) { int nleft = g.size(), nright = 0; each(es, g) if(!es->empty()) nright = max(nright, *max_element(es->begin(), es->end()) + 1); vi matchL(nleft, -1), matchR(nright, -1), prev(nleft), seen(nleft, -1); rep(i, nleft) { vi stk; stk.push_back(i); seen[i] = i; prev[i] = -1; while(!stk.empty()) { int v = stk.back(); stk.pop_back(); each(ui, g[v]) { int u = *ui; int j = matchR[u]; if(j == -1) { while(v != -1) { matchR[u] = v; swap(u, matchL[v]); v = prev[v]; } goto break_; } else if(seen[j] < i) { seen[j] = i; prev[j] = v; stk.push_back(j); } } } break_:; } return (int)matchL.size() - count(matchL.begin(), matchL.end(), -1); } int main() { int N; int M; while(~scanf("%d%d", &N, &M)) { vector S(N); rep(i, N) { char buf[51]; scanf("%s", buf); S[i] = buf; } vector g(N * M); rep(i, N) rep(j, M) if((i + j) % 2 == 0 && S[i][j] != '.') { static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 }; for(int d = 0; d < 4; ++ d) { int yy = i + dy[d], xx = j + dx[d]; if(yy < 0 || yy >= N || xx < 0 || xx >= M) continue; if(S[yy][xx] == '.') continue; g[i * M + j].push_back(yy * M + xx); } } int cnt[2] = {}; rep(i, N) rep(j, M) if(S[i][j] != '.') ++ cnt[(i + j) % 2]; int match = bipartiteMatching(g); int x = min(cnt[0], cnt[1]) - match; int y = cnt[0] + cnt[1] - match * 2 - x * 2; int ans = match * 100 + x * 10 + y; printf("%d\n", ans); } return 0; }