题目描述

John 得到一份地图，长 $H$ 宽 $W$，地图中 . 表示水，A 表示大陆，x 表示其他小岛。

他决定驾驶他的船绕大陆一圈，但并不想环绕其他小岛。

John 可以在任意有水的格子出发，求绕一周最小路径长度（一个格子可以经过任意多次）。

输入格式

第一行两个空格隔开正整数 $H$ 和 $W$（$3 \leq H,W\leq 1000$），

下来有 $H$ 行，每行 $W$ 个字符表示地图。

输出格式

一行一个整数，即绕一周最小路径长度。

输入输出样例 #1

输入 #1

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

输出 #1

62