题目描述

牧场中有一片小而连续的树木林，中间没有“空洞”。贝西想知道：绕着这片树林走一圈并回到起点需要走多远？她确信存在一种方法，从起点出发，通过水平、垂直或对角线移动（每步算作一个单位）到达连续的位置，并最终回到起点。从表面看，她认为无法通过对角线“穿过”树林。你的任务是计算她必须采取的最小步数。

幸运的是，贝西所在的牧场可以用一个$R$行$C$列（$1 \leq R \leq 50$，$1 \leq C \leq 50$）的网格表示。以下是一个典型示例：.表示牧场（贝西可以通行），X表示树林，*表示贝西的起点和终点，+标记了一条环绕树林的最短路径（即答案）：

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

图中所示的路径并非唯一的最短路径；贝西本可以从起点迈出一个对角线步，从而获得长度相近的解决方案。令贝西感到庆幸的是，她是从树林 “外部” 出发，而不是从某种可能会让寻找最优路径变得复杂的 “港湾” 区域出发。

输入格式

• 第1行：两个空格分隔的整数$R$和$C$。
• 第2到$R+1$行：每行包含$C$个字符（无空格），描述第$i$行的内容。

输出格式

• 单行输出一个整数，表示环绕树林所需的最小步数。

输入数据 1

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

输出数据 1

13  

题目来源

USACO 2006年1月银组竞赛