#1784. [Usaco2010 Jan]island

题目描述

 一个字符矩阵，'.'为海洋，'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  

数据范围与提示