题目描述

牧场里有树林，林子里没有坑，贝茜很想知道，最少几步能绕树林走一圈，最后回到起点.她能上下左右走，也能走对角线格子.

牧场被分成 $R$ 行 $C$ 列 $(1\leq R\leq 50,1\leq C\leq 50)$。下面是一张样例的地图，其中 . 表示贝茜可以走的空地，X 表示树林，* 表示起点。而贝茜走的最近的路已经特别地用 + 表示出来：

...+...
..+X+..
.+XXX+.
..+XXX+
..+X..+
...+++*

题目保证存在最短路径，且森林形成一个联通块。

输入格式

第一行两个正整数 $R,C$。

下面 $R$ 行，一个 $R \times C$ 的字符矩阵。

输出格式

一行一个整数表示答案。

6 7
.......
...X...
..XXX..
...XXX.
...X...
...*...

11