#1784. [Usaco2010 Jan]island

内存限制:64 MiB 时间限制:1 Sec

题目描述

一个字符矩阵,'.'为海洋,'A'为主岛,'x'为其它岛,保证所有'A'构成一个联通块,画一个圈,使得所有的'A'在圈内,所有的'x'在圈外,更具体的看样例,求这样的圈的最小周长

输入格式

Line 1: Two space-separated integers: H and W * Lines 2..H+1: Line i+1 contains contains W characters that are the elements of map row i (all '.' or 'x' or 'A')

输出格式

* Line 1: The minimum length of a path that Farmer John's cruise ship can take

样例

样例输入


			
12 19
...................
...................
.....A.............
.....A..x..........
..x..A.....AAAA....
.....A.....A..A....
.....AAAAAAAA.A....
........A.....A....
.xx...AAA...x.A....
......A............
...AAAAAAAAAAAAA...
...................


样例输出


			
62

数据范围与提示