using System; using System.Collections.Generic; using System.Linq; using System.IO; using static System.Console; using static System.Convert; using static System.Math; //using static System.Globalization.CultureInfo; using System.Text; class Program { private static void chmin(ref T num, T val) where T : IComparable => num = num.CompareTo(val) == 1 ? val : num; private static void chmax(ref T num, T val) where T : IComparable => num = num.CompareTo(val) == -1 ? val : num; static void Main(string[] args) { var pr = new Program(); var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); pr.Solve(); Console.Out.Flush(); } void Solve() { int n, m; Input.Make(out n, out m); var grid = Input.grid(n); var gh = new[] { 0, 0, 1, -1 }; var gw = new[] { 1, -1, 0, 0 }; var f = new MaxFlow(n * m + 2); var ctw = 0; var ctb = 0; for (var i = 0; i < n; i++) for (var j = 0; j < m; j++) if (grid[i][j] != '.') { if ((i + j) % 2 == 0) ctw++; else { ctb++; continue; } for(var k = 0; k < 4; k++) { var h = gh[k] + i; var w = gw[k] + j; if (!Inside(h, w, n, m)||grid[h][w]=='.') continue; f.AddDirectedEdge(i * m + j, h * m + w, 1); } } for(var i=0;i Inside(h, w, hw[0], hw[1]); public static bool Inside(int h, int w, int hh, int ww) => 0 <= h && h < hh && 0 <= w && w < ww; } public class Input { public static string read => ReadLine().Trim(); public static int[] ar => read.Split(' ').Select(int.Parse).ToArray(); public static int num => ToInt32(read); public static long[] arL => read.Split(' ').Select(long.Parse).ToArray(); public static long numL => ToInt64(read); public static T[] create(int n, Func f) => Enumerable.Repeat(0, n).Select(f).ToArray(); public static char[][] grid(int h) => create(h, _ => read.ToCharArray()); public static int[] ar1D(int n) => create(n, _ => num); public static long[] arL1D(int n) => create(n, _ => numL); public static string[] strs(int n) => create(n, _ => read); public static int[][] ar2D(int n) => create(n, _ => ar); public static long[][] arL2D(int n) => create(n, _ => arL); public static List[] edge(int n) => create(n, _ => new List()); public static T GetValue(string g) { var t = typeof(T); if (t == typeof(int)) return (T)(object)int.Parse(g); if (t == typeof(long)) return (T)(object)long.Parse(g); if (t == typeof(string)) return (T)(object)g; if (t == typeof(char)) return (T)(object)char.Parse(g); if (t == typeof(double)) return (T)(object)double.Parse(g); if (t == typeof(bool)) return (T)(object)bool.Parse(g); return default(T); } public static void Make(out T1 v1, out T2 v2) { v1 = Next(); v2 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3) { Make(out v1, out v2); v3 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4) { Make(out v1, out v2, out v3); v4 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5) { Make(out v1, out v2, out v3, out v4); v5 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6) { Make(out v1, out v2, out v3, out v4, out v5); v6 = Next(); } private static Queue sc; public static T Next(){ sc = sc ?? new Queue(); if (sc.Count == 0) foreach (var item in read.Split(' ')) sc.Enqueue(item);return GetValue(sc.Dequeue()); } public static void Next(ref T val) => val = Next(); public const long Inf = (long)1e18; public const double eps = 1e-6; public const string Alfa = "abcdefghijklmnopqrstuvwxyz"; public const int MOD = 1000000007; } public class Pair : IComparable> { public T1 v1 { get; set; } public T2 v2 { get; set; } public Pair() { v1 = Input.Next(); v2 = Input.Next(); } public Pair(T1 v1, T2 v2) { this.v1 = v1; this.v2 = v2; } public int CompareTo(Pair p) { var c = Comparer.Default.Compare(v1, p.v1); if (c == 0) c = Comparer.Default.Compare(v2, p.v2); return c; } public override string ToString() => $"{v1.ToString()} {v2.ToString()}"; public override bool Equals(object obj) => this == (Pair)obj; public override int GetHashCode() => v1.GetHashCode() ^ v2.GetHashCode(); public static bool operator ==(Pair p1, Pair p2) => p1.CompareTo(p2) == 0; public static bool operator !=(Pair p1, Pair p2) => p1.CompareTo(p2) != 0; public static bool operator >(Pair p1, Pair p2) => p1.CompareTo(p2) == 1; public static bool operator >=(Pair p1, Pair p2) => p1.CompareTo(p2) != -1; public static bool operator <(Pair p1, Pair p2) => p1.CompareTo(p2) == -1; public static bool operator <=(Pair p1, Pair p2) => p1.CompareTo(p2) != 1; } public class Pair : Pair, IComparable> { public T3 v3 { get; set; } public Pair() : base() { v3 = Input.Next(); } public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2) { this.v3 = v3; } public int CompareTo(Pair p) { var c = base.CompareTo(p); if (c == 0) c = Comparer.Default.Compare(v3, p.v3); return c; } public override string ToString() => $"{base.ToString()} {v3.ToString()}"; } public class MaxFlow { readonly List[] G; readonly int[] lv, iter; public MaxFlow(int V) { G = new List[V]; lv = new int[V]; iter = new int[V]; for (int i = 0; i < G.Length; i++) G[i] = new List(); } public void AddDirectedEdge(int from, int to, int cap) => addEdge(from, to, cap, 0); public void AddUndirectedEdge(int from, int to, int cap) => addEdge(from, to, cap, cap); void addEdge(int f, int t, int c1, int c2) { var a = new Edge(t, c1); var b = new Edge(f, c2); Edge.Link(a, b); G[f].Add(a); G[t].Add(b); } public int Execute(int src, int sink, int f = -1) { int flow = 0; if (f < 0) f = int.MaxValue; while (f > 0) { bfs(src); if (lv[sink] == 0) return flow; Array.Clear(iter, 0, iter.Length); int df; while ((df = dfs(src, sink, f)) > 0) { flow += df; f -= df; } } return flow; } void bfs(int s) { Array.Clear(lv, 0, lv.Length); var q = new Queue(); lv[s] = 1; q.Enqueue(s); while (q.Count > 0) { var v = q.Dequeue(); foreach (var e in G[v]) if (e.Cap > 0 && lv[e.To] == 0) { lv[e.To] = lv[v] + 1; q.Enqueue(e.To); } } } int dfs(int v, int t, int f) { if (v == t) return f; int ret = 0; for (; iter[v] < G[v].Count; iter[v]++) { var e = G[v][iter[v]]; if (e.Cap <= 0 || lv[v] >= lv[e.To]) continue; int df = dfs(e.To, t, Math.Min(f, e.Cap)); if (df <= 0) continue; e.Cap -= df; e.Rev.Cap += df; ret += df; f -= df; if (f == 0) break; } return ret; } class Edge { public static void Link(Edge e1, Edge e2) { e1.Rev = e2; e2.Rev = e1; } public int To { get; private set; } public Edge Rev { get; private set; } public int Cap { get; set; } public Edge(int t, int c) { To = t; Cap = c; } public override string ToString() { return string.Format("to: {0}, cap: {1}", To, Cap); } } }