#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include #include #include #include #include #include #include #include #include #include #include #include #include #define getchar getchar_unlocked #define putchar putchar_unlocked #define _rep(_1, _2, _3, _4, name, ...) name #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, b) rep4(i, a, b, 1) #define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c)) #define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__) using namespace std; using i8 = signed char; using i16 = signed short; using i64 = long long; using u8 = unsigned char; using u32 = unsigned; using u64 = unsigned long long; using f80 = long double; class MaximumMatching { // Note: each vertex is 1-indexed. public: struct edge { int from, to; }; MaximumMatching(int N, const vector& raw_edges) : N(N) { offsets.assign(N + 2, 0); for (auto& e : raw_edges) { offsets[e.from + 1] += 1; offsets[e.to + 1] += 1; } rep(i, N + 1) offsets[i + 1] += offsets[i]; edges.resize(2 * raw_edges.size()); for (auto& e : raw_edges) { edges[offsets[e.from]++] = {e.from, e.to}; edges[offsets[e.to]++] = {e.to, e.from}; } rep(i, N + 1) offsets[N + 1 - i] = offsets[N - i]; offsets[0] = 0; } int maximum_matching() { vector label(N + 1, -1), mate(N + 1, 0), first(N + 1, 0); vector que(N); int qh = 0, qt = 0; auto enqueue = [&] (int v) { que[qt++] = v; }; auto dequeue = [&] { return que[qh++]; }; auto encode = [&] (int eid) { return (N + 1) + eid; }; auto decode = [&] (int h) { return h - (N + 1); }; function< int(int) > find_first = [&] (int v) { return label[first[v]] < 0 ? first[v] : first[v] = find_first(first[v]); }; function< void(int, int) > rematch = [&] (int v, int w) { auto t = mate[v]; mate[v] = w; if (mate[t] != v) return; if (label[v] <= N) { mate[t] = label[v]; rematch(label[v], t); } else { auto& e = edges[decode(label[v])]; int x = e.from, y = e.to; rematch(x, y); rematch(y, x); } }; auto contract = [&] (int x, int y, int eid) { int r = find_first(x), s = find_first(y); if (r == s) return; auto h = encode(eid); label[r] = label[s] = -h; int join = -1; // lca while (1) { if (s != 0) swap(r, s); r = find_first(label[mate[r]]); if (label[r] == -h) { join = r; break; } else label[r] = -h; } for (auto v : { first[x], first[y] }) { for (; v != join; v = first[label[mate[v]]]) { label[v] = h; first[v] = join; enqueue(v); } } }; auto augment = [&] (int u) { label[u] = first[u] = 0; for (qh = qt = 0, que[qt++] = u; qh < qt; ) { auto x = dequeue(); rep(eid, offsets[x], offsets[x + 1]) { auto y = edges[eid].to; if (mate[y] == 0 && y != u) { mate[y] = x; rematch(x, y); return true; } else if (label[y] >= 0) { contract(x, y, eid); } else if (label[mate[y]] < 0) { label[mate[y]] = x; first[mate[y]] = y; enqueue(mate[y]); } } } return false; }; int matching = 0; rep(u, 1, N + 1) if (mate[u] == 0 && augment(u)) { matching += 1; if (N - 2 * matching <= 1) break; if (10 * qt < N) { label[0] = -1; rep(qi, qt) label[que[qi]] = label[mate[que[qi]]] = -1; } else fill(label.begin(), label.end(), -1); } /* vector< pair > matchings(matching); matching = 0; rep(u, 1, N + 1) if (mate[u] > u) { matchings[matching++] = {u, mate[u]}; } */ return matching; } private: int N; vector offsets; vector edges; }; void solve() { static char B[64][64]; int H, W; while (~scanf("%d %d", &H, &W)) { rep(y, H) scanf("%s", B[y]); vector edges; edges.reserve(2 * H * W); auto encode = [&] (int x, int y) { return y * W + x + 1; }; int counts[2] = {}; rep(y, H) rep(x, W) if (B[y][x] != '.') { counts[(x + y) & 1] += 1; if (x + 1 < W && B[y][x + 1] != '.') { edges.push_back({encode(x, y), encode(x + 1, y)}); } if (y + 1 < H && B[y + 1][x] != '.') { edges.push_back({encode(x, y), encode(x, y + 1)}); } } auto mm = MaximumMatching(H * W, edges).maximum_matching(); auto mc = min(counts[0], counts[1]); auto ans = 100 * mm + 10 * (mc - mm) + 1 * (counts[0] + counts[1] - 2 * mc); printf("%d\n", ans); } } int main() { clock_t beg = clock(); solve(); clock_t end = clock(); fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC); }