import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.InterruptedIOException; import java.util.ArrayDeque; import java.util.HashSet; import java.util.Queue; import java.util.Set; /** * Created by cteam040 on 10/22/16. */ public class Fence { private static final int NOTHING = Integer.MAX_VALUE; private static final int SHEEP = -2; private static final int WOLF = 0; private static int[][] field = null; private static int runTestCase(BufferedReader in, int h, int w) throws IOException { field = new int[h][w]; int minY = h-1; int minX = w-1; int maxY = 0; int maxX = 0; int[] wolfCoords = new int[2]; for (int i = 0; i < h; i++) { String line = in.readLine(); for (int j = 0; j < w; j++) { char c = line.charAt(j); switch (c) { case '.' : field[i][j] = NOTHING; break; case 'O' : field[i][j] = SHEEP; if (i < minY) minY = i; if (j < minX) minX = j; if (i > maxY) maxY = i; if (j > maxX) maxX = j; break; case 'X' : field[i][j] = WOLF; wolfCoords[0] = i; wolfCoords[1] = j; break; } } } if (w == 1) { if (minY < wolfCoords[0] && maxY > wolfCoords[0]) return -1; } if (h == 1) { if (minX < wolfCoords[1] && maxX > wolfCoords[1]) return -1; } int len = -1; int exitY = -1; int exitX = -1; Queue queue = new ArrayDeque<>(); queue.add(wolfCoords); while(!queue.isEmpty()) { int[] elem = queue.remove(); int y = elem[0]; int x = elem[1]; if (y >= maxY || y <= minY || x >= maxX || x <= minX) { len = field[y][x]; exitX = x; exitY = y; break; } if (y + 1 <= h-1) { if (field[y + 1][x] > field[y][x] + 1) { field[y + 1][x] = field[y][x] + 1; queue.add(new int[] {y + 1, x}); } } if (y -1 >= 0) { if (field[y -1][x] > field[y][x] + 1) { field[y -1][x] = field[y][x] + 1; queue.add(new int[] {y -1, x}); } } if (x + 1 <= w-1) { if (field[y][x + 1] > field[y][x] + 1) { field[y][x + 1] = field[y][x] + 1; queue.add(new int[] {y, x + 1}); } } if (x - 1 >= 0) { if (field[y][x-1] > field[y][x] + 1) { field[y][x-1] = field[y][x] + 1; queue.add(new int[] {y, x - 1}); } } } if (len == -1) { return -1; } int diff = 0; if (exitX == maxX) { int leftMax = 0; int rightMax = 0; for (int i = minY; i <= exitY - 1; i++) { for (int j = minX; j <= maxX; j++) { if (field[i][j] == SHEEP) { leftMax = j > leftMax ? j : leftMax; } } } for (int i = exitY + 1; i <= maxY; i++) { for (int j = minX; j <= maxX; j++) { if (field[i][j] == SHEEP) { rightMax = j > rightMax ? j : rightMax; } } } diff = Math.abs(leftMax - rightMax); } if (exitX == minX) { int leftMax = maxX; int rightMax = maxX; for (int i = minY; i <= exitY - 1; i++) { for (int j = minX; j <= maxX; j++) { if (field[i][j] == SHEEP) { leftMax = j < leftMax ? j : leftMax; } } } for (int i = exitY + 1; i <= maxY; i++) { for (int j = minX; j <= maxX; j++) { if (field[i][j] == SHEEP) { rightMax = j < rightMax ? j : rightMax; } } } diff = Math.abs(leftMax - rightMax); } if (exitY == maxY) { int leftMax = 0; int rightMax = 0; for (int i = minY; i <= maxY; i++) { for (int j = minX; j <= exitX - 1; j++) { if (field[i][j] == SHEEP) { leftMax = i > leftMax ? i : leftMax; } } } for (int i = minY; i <= maxY; i++) { for (int j = exitX + 1; j <= maxX ; j++) { if (field[i][j] == SHEEP) { rightMax = i > rightMax ? i : rightMax; } } } diff = Math.abs(leftMax - rightMax); } if (exitY == minY) { int leftMax = maxY; int rightMax = maxY; for (int i = minY; i <= maxY; i++) { for (int j = minX; j <= exitX - 1; j++) { if (field[i][j] == SHEEP) { leftMax = i < leftMax ? i : leftMax; } } } for (int i = minY; i <= maxY; i++) { for (int j = exitX + 1; j <= maxX ; j++) { if (field[i][j] == SHEEP) { rightMax = i < rightMax ? i : rightMax; } } } diff = Math.abs(leftMax - rightMax); } if (wolfCoords[0] > maxY || wolfCoords[0] < minY || wolfCoords[1] > maxX || wolfCoords[1] < minX) { diff++; } return ((len + 1) * 2) + 2 * (maxX - minX + 1) + 2 * (maxY - minY + 1) - (diff * 2); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); while (true) { String line = in.readLine(); if (line == null) break; String[] parts = line.split(" "); int h = Integer.parseInt(parts[0]); int w = Integer.parseInt(parts[1]); System.out.println(runTestCase(in, h, w)); } } }