题目描述

淘淘蓝蓝家小区有一片树林，这片树林没有坑，即任何一块空地都能不经过树林走到小区的边界。现在，聪明的你想知道，最少几步能绕树林走一圈，最后回到你出发的地方。你可以沿上下左右方向走一格，也可以走对角线格子，即可以沿八个方向行走到下一方格中。

这个树林可以看成 $n$ 行 $m$ 列的矩形。你可以行于空地之上，但不可以行走在有树的地方。

题目保证存在最短路径。

输入格式

第 1 行 2 个正整数 $n$ 和 $m$，表示这个小区是一个 $n$ 行 $m$ 列的矩形. 接下来 $n$ 行，每行 $m$ 个字符，表示这个小区的情况。 其中，“.”表示空地， “X” 表示树林， “*” 表示你的起点。

输出格式

输出 1 行，表示答案。

样例输入

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

输出

13

样例解释

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

“+ ”号表示你行走的路线。

数据范围

• 对于 20%的数据：保证只有 1 个格子有树；
• 对于另外 30%的数据：保证树林是个长方形；
• 对于 100%的数据：保证 $1 \leq n, m \leq 10$，保证树林沿上下左右 4 个方向连通；保证从每个空地(包括起点)出发沿上下左右 4 个方向直行一定有 2 个以上方向能够不碰到树就走到边界。