package No400番台; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Q421 { public static void main(String[] args) { new Q421().solver(); } int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; int h, w; char[][] choco; int[][] comp; void solver() { Scanner sc = new Scanner(System.in); h = sc.nextInt(); w = sc.nextInt(); choco = new char[h][w]; for (int i = 0; i < h; i++) { choco[i] = sc.next().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; for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { if (on_filed(x, y) && comp[y][x] == -1) { ArrayList[] g = new ArrayList[h * w]; for (int i = 0; i < h * w; i++) { g[i] = new ArrayList<>(); } 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); g[a].add(b); g[b].add(a); que.add(new Pair(nx, ny)); } } } int the_number_of_matchings = bipartiteMatching(g, (h * w) / 2); ans += the_number_of_matchings * 100; even -= the_number_of_matchings; odd -= the_number_of_matchings; color++; } } } // show_comp(); int common = Math.min(even, odd); ans += common * 10; even -= common; odd -= common; ans += even + odd; System.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(); } } }