package No400番台; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; public class Q421_0 { int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; int h, w; char[][] choco; int[][] comp; HashMap map = new HashMap<>(); @SuppressWarnings("unchecked") void solver() { h = ni(); w = ni(); choco = new char[h][w]; for (int i = 0; i < h; i++) { choco[i] = ns().toCharArray(); } comp = new int[h][w]; for (int i = 0; i < h; i++) { Arrays.fill(comp[i], -1); } int color = 0; int ans = 0; int odd = 0, even = 0; ArrayList[] g = new ArrayList[h * w]; for (int i = 0; i < h * w; i++) { g[i] = new ArrayList<>(); } for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { if (on_filed(x, y) && comp[y][x] == -1) { ArrayDeque que = new ArrayDeque<>(); que.add(new Pair(x, y)); while (!que.isEmpty()) { Pair p = que.poll(); if (comp[p.y][p.x] != -1) continue; comp[p.y][p.x] = color; if ((p.x + p.y) % 2 == 0) even++; else odd++; for (int i = 0; i < 4; i++) { int nx = p.x + dx[i]; int ny = p.y + dy[i]; if (on_filed(nx, ny) && comp[ny][nx] == -1) { int a = id(p.x, p.y); int b = id(nx, ny); map.put(a, new Pair(p.x, p.y)); map.put(b, new Pair(nx, ny)); g[a].add(b); g[b].add(a); que.add(new Pair(nx, ny)); } } } color++; } } } int the_number_of_matchings = bipartiteMatching(g, (h * w + 1) / 2); ans += the_number_of_matchings * 100; even -= the_number_of_matchings; odd -= the_number_of_matchings; // show_comp(); int common = Math.min(even, odd); ans += common * 10; even -= common; odd -= common; ans += even + odd; out.println(ans); } int id(int x, int y) { if ((y + x) % 2 == 0) return (y * w + x) / 2; else return (y * w + x) / 2 + (h * w - 1) / 2 + 1; } boolean on_filed(int x, int y) { if (0 <= x && x < w && 0 <= y && y < h && choco[y][x] != '.') { return true; } else return false; } class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } boolean augment(ArrayList[] g, int u, Integer[] matchTo, Boolean[] visited) { if (u < 0) return true; for (int v : g[u]) { if (!visited[v]) { visited[v] = true; if (augment(g, matchTo[v], matchTo, visited)) { matchTo[u] = v; matchTo[v] = u; return true; } } } return false; } int bipartiteMatching(ArrayList[] g, int L) { final int n = g.length; Integer[] matchTo = new Integer[n]; Arrays.fill(matchTo, -1); matching = new ArrayList<>(); int match = 0; for (int i = 0; i < L; i++) { Boolean[] visited = new Boolean[n]; Arrays.fill(visited, false); if (augment(g, i, matchTo, visited)) match++; } for (int i = 0; i < L; i++) { if (matchTo[i] > 0) matching.add(new Edge(i, matchTo[i])); } return match; } ArrayList matching; class Edge { int a; int b; Edge(int a, int b) { this.a = a; this.b = b; } } void show_comp() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { System.out.print((comp[i][j] == -1 ? "#" : comp[i][j]) + " "); } System.out.println(); } } static InputStream is; static PrintWriter out; static String INPUT = ""; public static void main(String[] args) throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); new Q421_0().solver(); out.flush(); } static long nl() { try { long num = 0; boolean minus = false; while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-')) ; if (num == '-') { num = 0; minus = true; } else { num -= '0'; } while (true) { int b = is.read(); if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } } } catch (IOException e) { } return -1; } static char nc() { try { int b = skip(); if (b == -1) return 0; return (char) b; } catch (IOException e) { } return 0; } static double nd() { try { return Double.parseDouble(ns()); } catch (Exception e) { } return 0; } static String ns() { try { int b = skip(); StringBuilder sb = new StringBuilder(); if (b == -1) return ""; sb.append((char) b); while (true) { b = is.read(); if (b == -1) return sb.toString(); if (b <= ' ') return sb.toString(); sb.append((char) b); } } catch (IOException e) { } return ""; } public static char[] ns(int n) { char[] buf = new char[n]; try { int b = skip(), p = 0; if (b == -1) return null; buf[p++] = (char) b; while (p < n) { b = is.read(); if (b == -1 || b <= ' ') break; buf[p++] = (char) b; } return Arrays.copyOf(buf, p); } catch (IOException e) { } return null; } public static byte[] nse(int n) { byte[] buf = new byte[n]; try { int b = skip(); if (b == -1) return null; is.read(buf); return buf; } catch (IOException e) { } return null; } static int skip() throws IOException { int b; while ((b = is.read()) != -1 && !(b >= 33 && b <= 126)) ; return b; } static boolean eof() { try { is.mark(1000); int b = skip(); is.reset(); return b == -1; } catch (IOException e) { return true; } } static int ni() { try { int num = 0; boolean minus = false; while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-')) ; if (num == '-') { num = 0; minus = true; } else { num -= '0'; } while (true) { int b = is.read(); if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } } } catch (IOException e) { } return -1; } }