import std.conv, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; } int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); } int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); } int root(int[] uf, int u) { return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u])); } bool connect(int[] uf, int u, int v) { u = uf.root(u); v = uf.root(v); if (u == v) return false; if (uf[u] > uf[v]) swap(u, v); uf[u] += uf[v]; uf[v] = u; return true; } int M, N; string[] A; int[][] G; int[] scores; // (discard, use) Tuple!(int, int) dfs(int u) { auto ret = tuple(0, scores[u]); foreach (v; G[u]) { auto res = dfs(v); ret[0] += max(res[0], res[1]); ret[1] += res[0]; } return ret; } void main() { try { for (; ; ) { M = readInt(); N = readInt(); A = new string[M + 2]; foreach (x; [0, M + 1]) { foreach (y; 0 .. N + 2) { A[x] ~= "."; } } foreach (x; 1 .. M + 1) { A[x] = "." ~ readToken() ~ "."; } M += 2; N += 2; auto uf = new int[M * N]; uf[] = -1; foreach (x; 0 .. M) foreach (y; 0 .. N) { if (A[x][y] == 'x') { foreach (dir; 0 .. 4) { const xx = x + [+1, +1, 0, -1, -1, -1, 0, +1][dir]; const yy = y + [0, +1, +1, +1, 0, -1, -1, -1][dir]; if (0 <= xx && xx < M && 0 <= yy && yy < N && A[xx][yy] == 'x') { uf.connect(x * N + y, xx * N + yy); } } } } int V = 1; auto ids = new int[][](M, N); foreach (x; 0 .. M) foreach (y; 0 .. N) { ids[x][y] = -1; } foreach (x; 0 .. M) foreach (y; 0 .. N) { if (A[x][y] == 'x' && uf[x * N + y] < 0) { ids[x][y] = V++; } } foreach (x; 0 .. M) foreach (y; 0 .. N) { if (A[x][y] == 'x') { const r = uf.root(x * N + y); ids[x][y] = ids[r / N][r % N]; } } debug { writeln("ids"); foreach (x; 0 .. M) { writeln(ids[x]); } } // 0-1 BFS from outside // (depth, last ring) auto q = DList!(Tuple!(int, int))(); auto d = new Tuple!(int, int)[][](M, N); auto vis = new bool[][](M, N); foreach (x; 0 .. M) foreach (y; 0 .. N) { d[x][y] = tuple(M * N, -1); vis[x][y] = false; } d[0][0] = tuple(0, 0); q.insertBack(tuple(0, 0)); for (; !q.empty; ) { const x = q.front[0]; const y = q.front[1]; q.removeFront; if (!vis[x][y]) { vis[x][y] = true; const cc = (A[x][y] == 'x') ? tuple(d[x][y][0] + 1, ids[x][y]) : d[x][y]; foreach (dir; 0 .. 4) { int xx = x + [+1, 0, -1, 0][dir]; int yy = y + [0, +1, 0, -1][dir]; if (0 <= xx && xx < M && 0 <= yy && yy < N) { if (d[xx][yy] > cc) { d[xx][yy] = cc; (A[x][y] == 'x') ? q.insertBack(tuple(xx, yy)) : q.insertFront(tuple(xx, yy)); } } } } } debug { writeln("d[][][0]"); foreach (x; 0 .. M) { writeln(d[x].map!"a[0]"); } writeln("d[][][1]"); foreach (x; 0 .. M) { writeln(d[x].map!"a[1]"); } } G = new int[][V]; scores = new int[V]; foreach (x; 0 .. M) foreach (y; 0 .. N) { if (A[x][y] == 'x' && uf[x * N + y] < 0) { G[d[x][y][1]] ~= ids[x][y]; scores[ids[x][y]] = -uf[x * N + y]; } } debug { writeln("G = ", G); writeln("scores = ", scores); } auto res = dfs(0); writeln(res[0]); } } catch (EOFException e) { } }